Show Menu
Cheatography

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

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

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.