Function of a Parser Takes the sequence of tokens produced by the scanner as its input and produces the syntax tree as its output. Parser Sequence of tokens Syntax-Tree

Symbol table: major inherited attribute and major data structure in a compiler Principal operations: – Insert: store the information provided by name declarations when processing these declarations – Lookup: retrieve the information associated to a name when that name is used in the associated code

Attributes – Any property of a programming language construct such as The data type of a variable The value of an expression The location of a variable in memory

A stack-based environment will result in a dangling reference when the procedure is exited if a local variable in a procedure can be returned to the caller The simplest example:

The memory of a typical computer: A register area; Addressable Random access memory (RAM): A code area; A data area. The code area is fixed prior to execution, and can be visualized as follows:

Why Compiler Writing machine language-numeric codes is time consuming and tedious

Main idea LL(1) Parsing uses an explicit stack rather than recursive calls to perform a parse An example: – a simple grammar for the strings of balanced parentheses: S→(S) S∣ε The following table shows the actions of a top￾down parser given this grammar and the string ( )

The idea of Recursive-Descent Parsing Viewing the grammar rule for a non-terminal A as a definition for a procedure to recognize an A The right-hand side of the grammar for A specifies the structure of the code for this procedure The Expression Grammar:

SLR(1), called simple LR(1) parsing, uses the DFA of sets of LR(0) items as constructed in the previous section SLR(1) increases the power of LR(0) parsing significant by using the next token in the input string – First, it consults the input token before a shift to make sure that an appropriate DFA transition exists

A bottom-up parser uses an explicit stack to perform a parse – The parsing stack contains tokens, nonterminals as well as some extra state information – The stack is empty at the beginning of a bottom-up parse, and will contain the start symbol at the end of a successful parse