Build Your Own Programming Language A developer’s comprehensive guide to crafting, compiling, and implementing programming… (Clinton L. Jeffery)（Z-Library）

Page 1

(This page has no text content)

Page 2

Build Your Own Programming Language Second Edition A developer’s comprehensive guide to crafting, compiling, and implementing programming languages Clinton L. Jeffery BIRMINGHAM—MUMBAI

Page 3

Build Your Own Programming Language Second Edition Copyright © 2024 Packt Publishing All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews. Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book. Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information. Senior Publishing Product Manager: Denim Pinto Acquisition Editor: Peer Reviews: Gaurav Gavas Project Editor: Parvathy Nair Content Development Editor: Elliot Dallow

Page 4

Copy Editor: Safis Editing Technical Editor: Aneri Patel Proofreader: Safis Editing Indexer: Hemangini Bari Presentation Designer: Ajay Patule Developer Relations Marketing Executive: Vidhi Vashisth First published: December 2021 Second edition: January 2024 Production reference: 2300124 Published by Packt Publishing Ltd. Grosvenor House 11 St Paul’s Square Birmingham B3 1RB, UK. ISBN 978-1-80461-802-8 www.packt.com

Page 5

Foreword In the dynamic world of computer science, the creation of a programming language stands as a testament to ingenuity and a deep understanding of computational principles. Build Your Own Programming Language is not just a guide; it is an invitation to delve into the complexity and beauty of programming language creation. At the helm of this voyage is Clinton L. Jeffery, a distinguished professor and Chair of the Department of Computer Science and Engineering at the New Mexico Institute of Mining and Technology. His academic journey, marked by degrees from the University of Washington and the University of Arizona, has been a path of relentless exploration in the realms of programming languages, program monitoring, and visualization, among others. His work culminates in the creation of the Unicon programming language, a testament to his expertise and vision. This book is structured to guide the reader through the nuanced process of developing a programming language. Beginning with motivations and types of language implementations, Jeffery sets the stage for understanding the fundamental “why” behind language design. He intricately discusses organizing a bytecode language and differentiates between programming languages and libraries, laying a solid foundation for both novices and experienced programmers. The detailed chapters delve into the heart of language design, parsing, and the construction of syntax trees, with practical examples and case studies

Page 6

like the development of Unicon and the Jzero language. Jeffery’s approach is meticulous, ensuring that readers grasp the essentials of technical requirements, lexical categories, context-free grammar, and symbol tables. This comprehensive coverage ensures that readers are not just following instructions but are truly understanding the principles at play. What makes this book exceptional is its blend of theoretical knowledge and practical application. Jeffery does not shy away from the complexities of designing graphics facilities or tackling syntax trees and symbol tables. Instead, he embraces these challenges, guiding the reader with clarity and insight. The inclusion of questions at the end of each chapter prompts critical thinking and reflection, reinforcing the overall learning experience. As you progress through Build Your Own Programming Language, you will find yourself not just acquiring knowledge, but also developing a new perspective on programming languages. They are not merely tools for tasks but are expressive mediums that reflect human creativity and problem- solving skills. Clinton L. Jeffery, with his extensive experience and pioneering work in Unicon, provides a comprehensive and enlightening guide for anyone interested in the art and science of programming language development. Whether you are a student, a professional programmer, or an enthusiast of computer science, this book is a beacon, illuminating the path to understanding and creating your own programming language. Welcome to a journey of discovery, creativity, and technical mastery in the world of programming languages! Imran Ahmad, PhD Senior Data Scientist, Canadian Federal Government

Page 7

Contributors About the author Clinton L. Jeffery is Professor and Chair of the Department of Computer Science and Engineering at the New Mexico Institute of Mining and Technology. He received his B.S. from the University of Washington, and M.S. and Ph.D. degrees from the University of Arizona, all in computer science. He has conducted research and written many books and papers on programming languages, program monitoring, debugging, graphics, virtual environments, and visualization. With colleagues, he invented the Unicon programming language, hosted at unicon.org. Steve Wampler, Sana Algaraibeh, and Phillip Thomas provided valuable feedback and suggestions for improving this book.

Page 8

About the reviewers Steve Wampler was awarded a Ph.D. in Computer Science by the University of Arizona. He has worked as an Associate Professor of Computer Science as well as a software designer for several major telescope projects, including the Gemini 8m telescopes project and the Daniel K Inouye solar telescope. He has been a software reviewer for a number of other major telescope systems and a technical reviewer for several other programming books. Sana Algaraibeh was awarded her Ph.D. in Computer Science from the University of Idaho. She joined the faculty at the New Mexico Institute of Mining and Technology as a Computer Science instructor in 2022. Prior to that, she worked in academia for 14+ years as a lecturer, trainer, team leader, instructional designer, and Computer Science department chair at universities in Jordan and Saudi Arabia. She teaches Internet and Web Programming, Object-Oriented Programming, Python for Data Science, Algorithms and Data Structures, and Introduction to Programming. Her area of scholarship is computer science education and compiler error messages. She is interested in developing computational solutions integrated with modern pedagogy.

Page 9

Join our community on Discord Join our community’s Discord space for discussions with the authors and other readers: https://discord.com/invite/zGVbWaxqbw OceanofPDF.com

Page 10

Contents Preface Who this book is for What this book covers To get the most out of this book Get in touch Section I: Programming Language Frontends 1. Why Build Another Programming Language? Motivations for writing your own programming language Types of programming language implementations Organizing a bytecode language implementation Languages used in the examples The difference between programming languages and libraries Applicability to other software engineering tasks Establishing the requirements for your language Case study – requirements that inspired the Unicon language Unicon requirement #1 – preserve what people love about Icon Unicon requirement #2 – support large-scale programs working on big data Unicon requirement #3 – high-level input/output for modern applications Unicon requirement #4 – provide universally implementable system interfaces Summary Questions 2. Programming Language Design Determining the kinds of words and punctuation to provide in your language Specifying the control flow Deciding on what kinds of data to support Atomic types Composite types Domain-specific types Overall program structure

Page 11

Completing the Jzero language definition Case study – designing graphics facilities in Unicon Language support for 2D graphics Adding support for 3D graphics Summary Questions 3. Scanning Source Code Technical requirements Lexemes, lexical categories, and tokens Regular expressions Regular expression rules Regular expression examples Using UFlex and JFlex Header section Regular expressions section Writing a simple source code scanner Running your scanner Tokens and lexical attributes Expanding our example to construct tokens Writing a scanner for Jzero The Jzero flex specification Unicon Jzero code Java Jzero code Running the Jzero scanner Regular expressions are not always enough Summary Questions 4. Parsing Technical requirements Syntax analysis Context-free grammars Writing context-free grammar rules Writing rules for programming constructs Using iyacc and BYACC/J Declaring symbols in the header section Advanced yacc declarations Putting together the yacc context-free grammar section

Page 12

Understanding yacc parsers Fixing conflicts in yacc parsers Syntax error recovery Putting together a toy example Writing a parser for Jzero The Jzero lex specification The Jzero yacc specification Unicon Jzero code Java Jzero parser code Running the Jzero parser Improving syntax error messages Adding detail to Unicon syntax error messages Adding detail to Java syntax error messages Using Merr to generate better syntax error messages Summary Questions 5. Syntax Trees Technical requirements Using GNU Make Learning about trees Defining a syntax tree type Parse trees versus syntax trees Creating leaves from terminal symbols Wrapping tokens in leaves Working with YACC’s value stack Wrapping leaves for the parser’s value stack Determining which leaves you need Building internal nodes from production rules Accessing tree nodes on the value stack Using the tree node factory method Forming syntax trees for the Jzero language Debugging and testing your syntax tree Avoiding common syntax tree bugs Printing your tree in a text format Printing your tree using dot Summary Questions

Page 13

Section II: Syntax Tree Traversals 6. Symbol Tables Technical requirements Establishing the groundwork for symbol tables Declarations and scopes Assigning and dereferencing variables Choosing the right tree traversal for the job Creating and populating symbol tables for each scope Adding semantic attributes to syntax trees Defining classes for symbol tables and symbol table entries Creating symbol tables Populating symbol tables Synthesizing the isConst attribute Checking for undeclared variables Identifying the bodies of methods Spotting uses of variables within method bodies Finding redeclared variables Inserting symbols into the symbol table Reporting semantic errors Handling package and class scopes in Unicon Mangling names Inserting self for member variable references Inserting self as the first parameter in method calls Testing and debugging symbol tables Summary Questions 7. Checking Base Types Technical requirements Type representation in the compiler Defining a base class for representing types Subclassing the base class for complex types Assigning type information to declared variables Synthesizing types from reserved words Inheriting types into a list of variables Determining the type at each syntax tree node Determining the type at the leaves Calculating and checking the types at internal nodes

Page 14

Runtime type checks and type inference in Unicon Summary Questions 8. Checking Types on Arrays, Method Calls, and Structure Accesses Technical requirements Checking operations on array types Handling array variable declarations Checking types during array creation Checking types during array accesses Checking method calls Calculating the parameters and return type information Checking the types at each method call site Checking the type at return statements Checking structured type accesses Handling instance variable declarations Checking types at instance creation Checking types of instance accesses Summary Questions 9. Intermediate Code Generation Technical requirements What is intermediate code? Why generate intermediate code? Learning about the memory regions in the generated program Introducing data types for intermediate code Adding the intermediate code attributes to the tree Generating labels and temporary variables An intermediate code instruction set Instructions Declarations Annotating syntax trees with labels for control flow Generating code for expressions Generating code for control flow Generating label targets for condition expressions Generating code for loops Generating intermediate code for method calls

Page 15

Reviewing the generated intermediate code Summary Questions 10. Syntax Coloring in an IDE Writing your own IDE versus supporting an existing one Downloading the software used in this chapter Adding support for your language to Visual Studio Code Configuring Visual Studio Code to do Syntax Highlighting for Jzero Visual Studio Code extensions using the JSON format JSON atomic types JSON collections File organization for Visual Studio Code extensions The extensions file The extension manifest Writing IDE tokenization rules using TextMate grammars Integrating a compiler into a programmer’s editor Analyzing source code from within the IDE Sending compiler output to the IDE Avoiding reparsing the entire file on every change Using lexical information to colorize tokens Extending the EditableTextList component to support color Coloring individual tokens as they are drawn Highlighting errors using parse results Summary Questions Section III: Code Generation and Runtime Systems 11. Preprocessors and Transpilers Understanding preprocessors A preprocessing example Identity preprocessors and pretty printers The preprocessor within the Unicon preprocessor Code generation in the Unicon preprocessor Transforming objects into classes Generating source code from the syntax tree Closure-based inheritance in Unicon The difference between preprocessors and transpilers

Page 16

Transpiling Jzero code to Unicon Semantic attributes for transpiling to Unicon A code generation model for Jzero The Jzero to Unicon transpiler code generation method Transpiling the base cases: names and literals Handling the dot operator Mapping Java expressions to Unicon Transpiler code for method calls Assignments Transpiler code for control structures Transpiling Jzero declarations Transpiling Jzero block statements Transpiling a Jzero class into a Unicon package that contains a class Summary Questions 12. Bytecode Interpreters Technical requirements Understanding what bytecode is Comparing bytecode with intermediate code Building a bytecode instruction set for Jzero Defining the Jzero bytecode file format Understanding the basics of stack machine operation Implementing a bytecode interpreter Loading bytecode into memory Initializing the interpreter state Fetching instructions and advancing the instruction pointer Instruction decoding Executing instructions Starting up the Jzero interpreter Writing a runtime system for Jzero Running a Jzero program Examining iconx, the Unicon bytecode interpreter Understanding goal-directed bytecode Leaving type information in at runtime Fetching, decoding, and executing instructions Crafting the rest of the runtime system

Page 17

Summary Questions 13. Generating Bytecode Technical requirements Converting intermediate code to Jzero bytecode Adding a class for bytecode instructions Mapping intermediate code addresses to bytecode addresses Implementing the bytecode generator method Generating bytecode for simple expressions Generating code for pointer manipulation Generating bytecode for branches and conditional branches Generating code for method calls and returns Handling labels and other pseudo-instructions in intermediate code Comparing bytecode assembler with binary formats Printing bytecode in assembler format Printing bytecode in binary format Linking, loading, and including the runtime system Unicon example – bytecode generation in icont Summary Questions 14. Native Code Generation Technical requirements Deciding whether to generate native code Introducing the x64 instruction set Adding a class for x64 instructions Mapping memory regions to x64 register-based address modes Using registers Starting from a null strategy Assigning registers to speed up the local region Converting intermediate code to x64 code Mapping intermediate code addresses to x64 locations Implementing the x64 code generator method Generating x64 code for simple expressions Generating code for pointer manipulation

Page 18

Generating native code for branches and conditional branches Generating code for method calls and returns Handling labels and pseudo-instructions Generating x64 output Writing the x64 code in assembly language format Going from native assembler to an object file Linking, loading, and including the runtime system Summary Questions Leave a review! 15. Implementing Operators and Built-In Functions Implementing operators Comparing adding operators to adding new hardware Implementing string concatenation in intermediate code Adding String concatenation to the bytecode interpreter Adding String concatenation to the native runtime system Writing built-in functions Adding built-in functions to the bytecode interpreter Writing built-in functions for use with the native code implementation Integrating built-ins with control structures Developing operators and functions for Unicon Writing operators in Unicon Developing Unicon’s built-in functions Summary Questions 16. Domain Control Structures Knowing when a new control structure is needed Scanning strings in Icon and Unicon Scanning environments and their primitive operations Eliminating excessive parameters via a control structure Rendering regions in Unicon Rendering 3D graphics from a display list Specifying rendering regions using built-in functions Varying levels of detail using nested rendering regions Creating a rendering region control structure

Page 19

Adding a reserved word for rendering regions Adding a grammar rule Checking wsection for semantic errors Generating code for a wsection control structure Summary Questions 17. Garbage Collection Grasping the importance of garbage collection Counting references to objects Adding reference counting to Jzero Reducing the number of heap allocations for strings Modifying the generated code for the assignment operator Modifying the generated code for method call and return The drawbacks and limitations of reference counting Marking live data and sweeping the rest Organizing heap memory regions Traversing the basis to mark live data Marking the block region Reclaiming live memory and placing it into contiguous chunks Summary Questions 18. Final Thoughts Reflecting on what was learned from writing this book Deciding where to go from here Studying programming language design Learning about implementing interpreters and bytecode machines Acquiring expertise in code optimization Monitoring and debugging program executions Designing and implementing IDEs and GUI builders Exploring references for further reading Studying programming language design Learning about implementing interpreters and bytecode machines Acquiring expertise in native code and code optimization Monitoring and debugging program executions

Page 20

Designing and implementing IDEs and GUI builders Summary Section IV: Appendix Appendix: Unicon Essentials Syntactic shorthand Running Unicon Using Unicon’s declarations and data types Declaring program components Using atomic data types Numeric Textual Aggregating multiple values using structure types Classes Lists Tables Sets Files Other types Evaluating expressions Forming expressions using operators Invoking procedures, functions, and methods Iterating and selecting what and how to execute Generators Debugging and environmental issues Learning the basics of the UDB debugger Environment variables Preprocessor Preprocessor commands Built-in macro definitions Function mini-reference Selected keywords Answers Other Books You May Enjoy Index OceanofPDF.com