Show Menu

Paramater Passing Mechanisms

Actual parameter is evaluated. It's value is placed in a the locating of the corres­ponding former parameter of the called procedure.
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.


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.
Ambiguous 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 name and an optional attribute value.
a descri­ption of the form that lexemes of a token may take.
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)

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

Associ­ativity of Operators

Addition, subtra­ction, multip­lic­ation and division.
Expone­nti­ation, "­C" =

Syntax­-Di­rected Transl­ation

Done by attaching rules or program fragments to produc­tions in grammars.
expr1 + term
Sum of two subexp­res­sions
In pseudo­-code:

Lexical Analyzer

does not require tokeni­zation.
2.Lexical 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

-- 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 nonter­minals (syntactic values).
3. A set of produc­tions. Each production consists of: (a) a nonter­minal 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.
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.
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.
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 ->

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
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


No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.