Paramater Passing Mechanisms
Actual parameter is evaluated. It's value is placed in a the locating of the corresponding former parameter of the called procedure.
Address of the actual parameter is passed to the value of the corresponding formal parameters. 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 fundamental problem of compilers).
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.
Top-down method for syntax analysis. Set of recursive procedures is used to process the input. Predictive parsing relies on the information about the first symbols that can be generated by a production body.
Tokens, Patterns and Lexemes
token name and an optional attribute value.
a description 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 programming language describes the proper form of its programs.
defines what its programs mean.
naturally describes the hierarchical structure of most programming languages.
Associativity of Operators
Addition, subtraction, multiplication and division.
Exponentiation, "C" =
Done by attaching rules or program fragments to productions in grammars.
expr1 + term
Sum of two subexpressions
does not require tokenization.
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 productions into single steps
- separate parsing from semantic checking
- Can manipulate abstract syntax after concrete syntax has been checked
- Can use syntax tree as intermediate representation
-- a node represents program construct e.g. node for an operator
-- children represent components of the construct e.g. nodes for operands
1. A set of terminal symbols (tokens). Elementary symbols of the language defined in its own grammar.
2. A set of nonterminals (syntactic values).
3. A set of productions. Each production consists of: (a) a nonterminal which is the head of left side of the production, (b) an arrow, and (c) a sequence of terminals or non-terminals.
4. A designation of one of the nonterminals as the start symbol.
The top-down construction of a parse tree is done by starting at the door, labelled with the starting nonterminal statement, and repeatedly parsing.
At node N, labelled with a nonterminal A, select one of the productions 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 constructed, typically the leftmost unexpanded nonterminal of the tree.
Reads characters from input and groups them into "token objects." 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 characters.
Map from identifiers to meanings. Keep track of
- binding: associating 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