How do I create a Programming Language? #1

INVESTING
[1] Webull (You can get 3 free stocks setting up a webull account today): https://a.webull.com/8XVa1znjYxio6ESdff

TRANSCRIPT

Why Lex & Yacc? or Why Flex & Bison?

If you are watching this video, you must be some type of programmer or you may be interested in programming. You may see languages like C, Java, Python, and hundreds of others and wondered at some point of time: How do you create a programming language? We are going to answer that question here and also build our own system that analysis's the declaration section of a C program.

A computer language is like any other spoken language. It has it’s own:
- tokens
- and Grammar

Tokens are a set of symbols with their own meaning and are the building blocks for a “language”. Tokens can be lowercase alphabets, uppercase alphabets, punctuation or even special symbols.

Every language has it’s own “grammar” as well. This involves the arrangement of the tokens to form something of meaning. So, if tokens can be described as a set of symbols, then it is the grammar that generates phrases and sentences.

We can define a phrase as a sequence of 1 or more “word tokens” with the correct part of speech. So, a phrase could be defined as a “adverb with one or more adjectives followed by a noun”. These phrases in turn can be combined to form sentences.

By defining various tokens (both single character and multi character) and defining how these tokens should appear, we have have effectively defined the structure of English Language!

You can create A-N-Y language you want just by knowing the tokens and the grammar. For programming, instead of word tokens, we would have Keywords, Identifiers, Numbers, and Special symbols as tokens.

Now the big question thats on everyone’s mind : How do you implement this? You can generate tokens in a language tool called LEX which is short for “lexical analyser”. In this .l file (or fl file for flex), you generate your own tokens. LEX files are actually converted into C behind the scenes.

Once the tokens are defined, how do we define the grammar of our new language? This is done using Yacc or Bison. YACC stands for “Yet another Compiler Compiler”.

You take the tokens generated by Lex and pass it to a parser. This parser is written in YACC .Yacc takes a concise description of a grammar and produces a C routine that can parse that grammar. This Yacc parser automatically detects whenever a sequence of input tokens matches one of the rules in the grammar and takes some action as defined. It also detects a syntax error whenever its input does not match any of the rules.

I’ve said through this video “We are gonna create a language”. What I actually mean is, we are going to create some “program” that understands a custom set of tokens and grammar or syntax rules.

Those familiar with programming will know that this is one task of a “compiler”. Of these 7 phases of compiler design, we are only concerned with the first 3: performing Lexical analysis, syntax analysis and semantic analysis.

The lex file will take care of the “lexical analysis” while the yacc file will take care of both syntax and semantic analysis. How exactly does this happen? I’ll explain these 3 phases.

SCANNER

The source file, which is the C code in this case, is passed to our “Scanner” or “Lexical Analyser” or “Lexer”. This lexer will tokenize this input to generate a stream of tokens. These tokens represent the “alphabets” of our language that are to be recognized and processed.
We define these tokens in our Lex file. Note that the lex file is the Scanner Generator. It will create a C program called lex.yy.c and this file is the scanner.

PARSER

The stream of tokens produced is now fed into a Yacc Parser. The grammar for the sequence of tokens is specified by the parser. A “parse tree” is generated and the program is checked to see if it follows this Context Free Grammar. YACC will generate a C file called y.tab.c which will act as the parser.


SEMANTIC ANALYSIS

Semantic analysis involves checking if the parse tree constructed follows the rules of language.


Lex.yy.c is created from the lex file using LEX, the language tool. While y.tab.c is created from the yacc file using the YACC tool. The YACC tool also generates a harder file y.tab.h which is used by LEX to generate lex.yy.c. The two C files work together to form a Language Processor, which converts the given source code to Compiled or Interpreted Code.

Now that you know how lex & yacc work, we are going to install and work with them in the next video.