Show Menu

Compilers Cheat Sheet by

compilers

Paramater Passing Mechanisms

Call-­by-­value:
Actual parameter is evaluated. It's value is placed in a the locating of the corres­ponding former parameter of the called procedure.
Call-­by-­ref­ere­nce:
Address of the actual parameter is passed to the value of the corres­ponding formal parame­ters. The expression is evaluated before the call, and its value is stored in a location of its own.

Parsing

A string of terminals -> Figure out how to derive it from the start symbol of the grammar (reports errors) (most fundam­ental problem of compil­ers).
Parse Tree: shows how the start symbol of a grammar derives a string in the language.
Ambi­guous grammar: a grammar is said to be ambiguous when there are more than one parse trees for generating a given string of terminals.

Predictive Parsing

Top-down method for syntax analysis. Set of recursive procedures is used to process the input. Predictive parsing relies on the inform­ation about the first symbols that can be generated by a production body.

Tokens, Patterns and Lexemes

Token
token name and an optional attribute value.
Pattern
a descri­ption of the form that lexemes of a token may take.
Lexeme
sequence of characters in the source program that matches a pattern for the token and is identified by the lexical analyzer as an instance of that token.
 

Syntax Directed Translator (SYNTAX)

Syntax:
of a progra­mming language describes the proper form of its programs.
Seman­tics:
defines what its programs mean.
Grammar:
naturally describes the hierar­chical structure of most progra­mming languages.

Associ­ativity of Operators

Left-a­sso­ciative
Addition, subtra­ction, multip­lic­ation and division.
Right-­ass­oci­ative
Expone­nti­ation, "­C" =

Syntax­-Di­rected Transl­ation

Done by attaching rules or program fragments to produc­tions in grammars.
expr
->
expr1 + term
 
Sum of two subexp­res­sions
In pseudo­-co­de:
 
Translate
expr1;
 
Translate
term;
 
Handle
+;

Lexical Analyzer

1.Sc­ann­ing
does not require tokeni­zation.
2.Le­xical Analysis
produces tokes from the output of the scanner.

Abstract Syntax Tree (AST)

- condensed form of parse trees
- represent the syntax of a program.
- collapse chains of produc­tions into single steps
- separate parsing from semantic checking
- Can manipulate abstract syntax after concrete syntax has been checked
- Can use syntax tree as interm­ediate repres­ent­ation

STRUCTURE:
-- a node represents program construct e.g. node for an operator
-- children represent components of the construct e.g. nodes for operands
 

Contex­t-Free Grammar

1. A set of terminal symbols (tokens). Elementary symbols of the language defined in its own grammar.
2. A set of nonte­rmi­nals (syntactic values).
3. A set of produ­cti­ons. Each production consists of: (a) a nonte­rminal which is the head of left side of the produc­tion, (b) an arrow, and (c) a sequence of terminals or non-te­rmi­nals.
4. A design­ation of one of the nonter­minals as the start symbol.

Top-Down Parsing

The top-down constr­uction of a parse tree is done by starting at the door, labelled with the starting nonter­minal statement, and repeatedly parsing.
1.
At node N, labelled with a nonter­minal A, select one of the produc­tions for A and construct a children at N for the symbols in the production body.
2.
Find the next node at which a subtree is to be constr­ucted, typically the leftmost unexpanded nonter­minal of the tree.

Lexical Analysis

Reads characters from input and groups them into "­token object­s." Along with a terminal symbol that is used for parsing decisions.
Token
->
Terminal + More Info.
General approach to reading ahead on the input.
Maintain an input buffer from which the lexical analyzer can read and push back charac­ters.
RegEx ->
NFA
->DFA

Symbol Tables

Map from identi­fiers to meanings. Keep track of
- binding: associ­ating a name with a location
- scope: where in the program a name has meaning
USAGE:
1. Lexical Analyzer: add entries to ST
2. Parser: add type info, discover scope
3. Semantic Analyzer: use type info to find semantic errors
4. Code generator: determine where data are located, generate code to access locations

Download the Compilers Cheat Sheet

2 Pages
//media.cheatography.com/storage/thumb/nsuarezcanton_compilers.750.jpg

PDF (recommended)

Alternative Downloads

Share This Cheat Sheet!

 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.