book

Build Your Own Programming Language - Second Edition

Name: Build Your Own Programming Language - Second Edition
Author: Clinton L. Jeffery
ISBN: 9781804618028

by Clinton L. Jeffery

January 2024

Beginner to intermediate

556 pages

13h 22m

English

Packt Publishing

Read now

Unlock full access

Preface
Who this book is forWhat this book coversTo get the most out of this bookGet in touch
Section I: Programming Language Frontends
Why Build Another Programming Language?
Motivations for writing your own programming languageTypes of programming language implementationsOrganizing a bytecode language implementationLanguages used in the examplesThe difference between programming languages and librariesApplicability to other software engineering tasksEstablishing the requirements for your languageCase study – requirements that inspired the Unicon languageUnicon requirement #1 – preserve what people love about IconUnicon requirement #2 – support large-scale programs working on big dataUnicon requirement #3 – high-level input/output for modern applicationsUnicon requirement #4 – provide universally implementable system interfacesSummaryQuestions
Programming Language Design
Determining the kinds of words and punctuation to provide in your languageSpecifying the control flowDeciding on what kinds of data to supportAtomic typesComposite typesDomain-specific typesOverall program structureCompleting the Jzero language definitionCase study – designing graphics facilities in UniconLanguage support for 2D graphicsAdding support for 3D graphicsSummaryQuestions
Scanning Source Code
Technical requirementsLexemes, lexical categories, and tokensRegular expressionsRegular expression rulesRegular expression examplesUsing UFlex and JFlexHeader sectionRegular expressions sectionWriting a simple source code scannerRunning your scannerTokens and lexical attributesExpanding our example to construct tokensWriting a scanner for JzeroThe Jzero flex specificationUnicon Jzero codeJava Jzero codeRunning the Jzero scannerRegular expressions are not always enoughSummaryQuestions
Parsing
Technical requirementsSyntax analysisContext-free grammarsWriting context-free grammar rulesWriting rules for programming constructsUsing iyacc and BYACC/JDeclaring symbols in the header sectionAdvanced yacc declarationsPutting together the yacc context-free grammar sectionUnderstanding yacc parsersFixing conflicts in yacc parsersSyntax error recoveryPutting together a toy exampleWriting a parser for JzeroThe Jzero lex specificationThe Jzero yacc specificationUnicon Jzero codeJava Jzero parser codeRunning the Jzero parserImproving syntax error messagesAdding detail to Unicon syntax error messagesAdding detail to Java syntax error messagesUsing Merr to generate better syntax error messagesSummaryQuestions
Syntax Trees
Technical requirementsUsing GNU MakeLearning about treesDefining a syntax tree typeParse trees versus syntax treesCreating leaves from terminal symbolsWrapping tokens in leavesWorking with YACC’s value stackWrapping leaves for the parser’s value stackDetermining which leaves you needBuilding internal nodes from production rulesAccessing tree nodes on the value stackUsing the tree node factory methodForming syntax trees for the Jzero languageDebugging and testing your syntax treeAvoiding common syntax tree bugsPrinting your tree in a text formatPrinting your tree using dotSummaryQuestions
Section II: Syntax Tree Traversals
Symbol Tables
Technical requirementsEstablishing the groundwork for symbol tablesDeclarations and scopesAssigning and dereferencing variablesChoosing the right tree traversal for the jobCreating and populating symbol tables for each scopeAdding semantic attributes to syntax treesDefining classes for symbol tables and symbol table entriesCreating symbol tablesPopulating symbol tablesSynthesizing the isConst attributeChecking for undeclared variablesIdentifying the bodies of methodsSpotting uses of variables within method bodiesFinding redeclared variablesInserting symbols into the symbol tableReporting semantic errorsHandling package and class scopes in Unicon Mangling namesInserting self for member variable referencesInserting self as the first parameter in method callsTesting and debugging symbol tablesSummaryQuestions
Checking Base Types
Technical requirementsType representation in the compilerDefining a base class for representing typesSubclassing the base class for complex typesAssigning type information to declared variablesSynthesizing types from reserved wordsInheriting types into a list of variablesDetermining the type at each syntax tree nodeDetermining the type at the leavesCalculating and checking the types at internal nodesRuntime type checks and type inference in UniconSummaryQuestions

Checking Types on Arrays, Method Calls, and Structure Accesses
Technical requirementsChecking operations on array typesHandling array variable declarationsChecking types during array creationChecking types during array accessesChecking method callsCalculating the parameters and return type informationChecking the types at each method call siteChecking the type at return statementsChecking structured type accessesHandling instance variable declarationsChecking types at instance creationChecking types of instance accessesSummaryQuestions
Intermediate Code Generation
Technical requirementsWhat is intermediate code?Why generate intermediate code?Learning about the memory regions in the generated programIntroducing data types for intermediate codeAdding the intermediate code attributes to the treeGenerating labels and temporary variablesAn intermediate code instruction setInstructionsDeclarationsAnnotating syntax trees with labels for control flowGenerating code for expressionsGenerating code for control flowGenerating label targets for condition expressionsGenerating code for loopsGenerating intermediate code for method callsReviewing the generated intermediate codeSummaryQuestions
Syntax Coloring in an IDE
Writing your own IDE versus supporting an existing oneDownloading the software used in this chapterAdding support for your language to Visual Studio CodeConfiguring Visual Studio Code to do Syntax Highlighting for JzeroVisual Studio Code extensions using the JSON formatJSON atomic typesJSON collectionsFile organization for Visual Studio Code extensionsThe extensions fileThe extension manifestWriting IDE tokenization rules using TextMate grammarsIntegrating a compiler into a programmer’s editorAnalyzing source code from within the IDESending compiler output to the IDEAvoiding reparsing the entire file on every changeUsing lexical information to colorize tokensExtending the EditableTextList component to support colorColoring individual tokens as they are drawnHighlighting errors using parse resultsSummaryQuestions
Section III: Code Generation and Runtime Systems
Preprocessors and Transpilers
Understanding preprocessorsA preprocessing exampleIdentity preprocessors and pretty printersThe preprocessor within the Unicon preprocessorCode generation in the Unicon preprocessorTransforming objects into classesGenerating source code from the syntax treeClosure-based inheritance in UniconThe difference between preprocessors and transpilersTranspiling Jzero code to UniconSemantic attributes for transpiling to UniconA code generation model for JzeroThe Jzero to Unicon transpiler code generation methodTranspiling the base cases: names and literalsHandling the dot operatorMapping Java expressions to UniconTranspiler code for method callsAssignmentsTranspiler code for control structuresTranspiling Jzero declarationsTranspiling Jzero block statementsTranspiling a Jzero class into a Unicon package that contains a classSummaryQuestions
Bytecode Interpreters
Technical requirementsUnderstanding what bytecode isComparing bytecode with intermediate codeBuilding a bytecode instruction set for JzeroDefining the Jzero bytecode file formatUnderstanding the basics of stack machine operationImplementing a bytecode interpreterLoading bytecode into memoryInitializing the interpreter stateFetching instructions and advancing the instruction pointerInstruction decodingExecuting instructionsStarting up the Jzero interpreterWriting a runtime system for JzeroRunning a Jzero programExamining iconx, the Unicon bytecode interpreterUnderstanding goal-directed bytecodeLeaving type information in at runtimeFetching, decoding, and executing instructionsCrafting the rest of the runtime systemSummaryQuestions
Generating Bytecode
Technical requirementsConverting intermediate code to Jzero bytecodeAdding a class for bytecode instructionsMapping intermediate code addresses to bytecode addressesImplementing the bytecode generator methodGenerating bytecode for simple expressionsGenerating code for pointer manipulationGenerating bytecode for branches and conditional branchesGenerating code for method calls and returnsHandling labels and other pseudo-instructions in intermediate codeComparing bytecode assembler with binary formatsPrinting bytecode in assembler formatPrinting bytecode in binary formatLinking, loading, and including the runtime systemUnicon example – bytecode generation in icontSummaryQuestions
Native Code Generation
Technical requirementsDeciding whether to generate native codeIntroducing the x64 instruction setAdding a class for x64 instructionsMapping memory regions to x64 register-based address modesUsing registersStarting from a null strategyAssigning registers to speed up the local regionConverting intermediate code to x64 codeMapping intermediate code addresses to x64 locationsImplementing the x64 code generator methodGenerating x64 code for simple expressionsGenerating code for pointer manipulationGenerating native code for branches and conditional branchesGenerating code for method calls and returnsHandling labels and pseudo-instructionsGenerating x64 outputWriting the x64 code in assembly language formatGoing from native assembler to an object fileLinking, loading, and including the runtime systemSummaryQuestionsLeave a review!
Implementing Operators and Built-In Functions
Implementing operatorsComparing adding operators to adding new hardwareImplementing string concatenation in intermediate codeAdding String concatenation to the bytecode interpreterAdding String concatenation to the native runtime systemWriting built-in functionsAdding built-in functions to the bytecode interpreterWriting built-in functions for use with the native code implementationIntegrating built-ins with control structuresDeveloping operators and functions for UniconWriting operators in UniconDeveloping Unicon’s built-in functionsSummaryQuestions
Domain Control Structures
Knowing when a new control structure is neededScanning strings in Icon and UniconScanning environments and their primitive operationsEliminating excessive parameters via a control structureRendering regions in UniconRendering 3D graphics from a display listSpecifying rendering regions using built-in functionsVarying levels of detail using nested rendering regionsCreating a rendering region control structureAdding a reserved word for rendering regionsAdding a grammar ruleChecking wsection for semantic errorsGenerating code for a wsection control structureSummaryQuestions
Garbage Collection
Grasping the importance of garbage collectionCounting references to objectsAdding reference counting to JzeroReducing the number of heap allocations for stringsModifying the generated code for the assignment operatorModifying the generated code for method call and returnThe drawbacks and limitations of reference countingMarking live data and sweeping the restOrganizing heap memory regionsTraversing the basis to mark live dataMarking the block regionReclaiming live memory and placing it into contiguous chunksSummaryQuestions
Final Thoughts
Reflecting on what was learned from writing this bookDeciding where to go from hereStudying programming language designLearning about implementing interpreters and bytecode machinesAcquiring expertise in code optimizationMonitoring and debugging program executionsDesigning and implementing IDEs and GUI buildersExploring references for further readingStudying programming language designLearning about implementing interpreters and bytecode machinesAcquiring expertise in native code and code optimizationMonitoring and debugging program executionsDesigning and implementing IDEs and GUI buildersSummary
Section IV: Appendix
Appendix: Unicon Essentials
Syntactic shorthandRunning UniconUsing Unicon’s declarations and data typesDeclaring program componentsUsing atomic data typesNumericTextualAggregating multiple values using structure typesClassesListsTablesSetsFilesOther typesEvaluating expressionsForming expressions using operatorsInvoking procedures, functions, and methodsIterating and selecting what and how to executeGeneratorsDebugging and environmental issuesLearning the basics of the UDB debuggerEnvironment variablesPreprocessorPreprocessor commandsBuilt-in macro definitionsFunction mini-referenceSelected keywords
Answers
Other Books You May Enjoy
Index

Content preview from Build Your Own Programming Language - Second Edition

5 Syntax Trees

The preceding two chapters covered lexical and syntax analysis, the first two phases of a compiler. Next, we will need to perform semantic analysis and code generation, but those phases will need some information to work from. The parser we constructed in the last chapter can detect and report syntax errors, which is a big, important job. When there is no syntax error, you need to build a data structure during parsing that represents the whole program logically. This data structure is based on how the different tokens and larger pieces of the program are grouped together. A syntax tree is a tree data structure that records the branching structure of the grammar rules used by the parsing algorithm to check the syntax of an input ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781804618028

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Build Your Own Programming Language - Second Edition

by Clinton L. Jeffery

5

Syntax Trees

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.