Compiler

Check if program is legal. If not, throws an error.

Generates intermediate representation (intermediate code?).

Multiple front ends can use the same back end? what does this mean?

Using IR makes it easier to port the compiler to different CPUs/architectures.

Translates intermediate representation into target code (Ex.: C -> Assembly).

Reads in strings and converts groups them into “lexemes.” A lexeme is a sequence of tokens that matches the pattern for a token. For example, in C, ’<=’ would be a lexeme corresponding to ’LESS_THANOREQUAL’. A lexer will translate lexemes into tokens.

A token here would be some piece of meaningful data which can be used in operations?

Skips whitespace & comments

Keeps track of lines/columns to properly report errors.

Scanner gives parser a token

A lexer does not detect errors, except illegal chars.

Creates a syntax tree

Parser gets token from scanner via getNextToken()

Check operations, catches anything illegal

Generates IR

Optimizes code

Generates the code which can be executed by the specific machine

Compilers often use symbol tables. When a compiler encounters and identifier it doesn’t recognize, it inserts it into the symbol table. Next time it finds this identifier, it can simply just reference the symbol table.

This is where we define patterns, aka regexps, and #includes. For example:

%{
#include <stdio.h>
#inlcude <stdlib.h>
}%
DIGIT        [0-9]
CommentStart "//"
ID           [a-zA-Z][a-zA-Z0-9]

Rules take the form pattern action.

The actual code of the program.

Flex has a scanner implemented as a fucntion:

int yylex();

• This returns which token is matched (int).
• The lexeme is stored int yytext(a char *) (what is this?)
• The lexeme length is stored in yyleng

A model that consists of:

• S, a set of states
• /Sigma , the input alphatbet
• A state s elem S, the start state
• F subset S, a set of final states
• Move, transitions between states

A mathematical model that consists of the same things as a DFA, except for the move function.

Basically, a DFA which may have the same option (a self loop, a to next state) leading to multiple states.h

A mathematical model that consists of the same things as a DFA, except for the move function.

Basically, a DFA which may have the same option (a self loop, a to next state) leading to multiple states.h

Simulating one can be inefficient. Can produce exponential running time. To fix this, we can build an equivalent DFA.

Parsing i th process of determining whether a string of tokens can be produced by a grammar

Most parsing methods take two forms:

LR parsers care about what has been in the previous input. LL parsers do not, they only care about the current token. We replace input tokens with language tokens (?) if applicatble.

These are more powerful that LL parsers, they, for example, don’t have the left-recursive issue.

• Move the first token from input stream into the stack
• Replace token in stack with some rule “T” if applicable
• Reduce stack as much as possible
• If reduced as much as possible, move next input token into stack
• Repeat step 2 until EOF is reached
• If possible, reduce
• You’re done

The parse tree is constructed beginning at the leaves and going towards the root.

A symbol table stores all the symbols encountered within a program. These symbols are generally identifiers (variables, constants).

When a complier encounters a new identifier, it adds an entry for that identifier into the symbol table. If the compiler encounters existing identifiers, it check the symbol table for scope, value, etc.

Each entry in the symbol table also generally stores the:

• Value
• Data type
• Scope
• Number of parameters
• And other things as needed

A symbol table is often implemented with the use of some data structure, more often than not, a hash map.

Add the symbol table file

A string table is used to store strings that are found in the code. If multiple strings are found in the same place within the code, instead of storing multiple distinct references to the string, the string can be store as an indexed entry within a string array.

String table can be linear, or can be implemented via a hashmap.

The symbol table and string table are fairly similar concept. The difference between them can be a bit confusing.

The primary function of a string table is to optimize the storage and loading of data. This leads to the system running faster and using less memory. When an identifier is encountered in the source code, its text is stored in the string table (if not already present). The compiler uses the string table to handle the textual aspect of the identifier efficiently.

A symbol table contains much more information than this. It contains information about each identifier in the table as described above. The same identifier also has an entry in the symbol table, but with additional contextual information. The symbol table entry links to the string table for the identifier’s name but also includes information like its type, scope, and usage within the program.

An abstract syntax tree is arguably the most complicated structure out of these three. The semantics of a program can be represented by an abstract syntax tree. The tree is abstract in the way that it omits certain elemnts like parantheses or semicolons which are not necessary for understanding the syntax.

An abstract syntax tree is made out of two parts:

• Nodes

  Nodes can represent “points” in source code. A node can store literals (constants), identifiers (variables), or more complex things like expressions, statements, and control structures (loops, conditionals).

• Edges

  The edges simply link the nodes together, creating an otherwise sporadic pool of nodes into a readable data structure.