by Dinesh Thakur

Syntax directed definition specifies the values of attributes by associating semantic rules with the grammar productions.

It is a context free grammar with attributes and rules together which are associated with grammar symbols and productions respectively.

The process of syntax directed translation is two-fold:

• Construction of syntax tree and

• Computing values of attributes at each node by visiting the nodes of syntax tree.

by Dinesh Thakur

• An efficient program should not terminate on an parse error.

• It must recover to parse the rest of the input and check for subsequent errors.

• For one line input, the routine yyparse() can be made to return 1 on error and then calls yyparse() again.

by Dinesh Thakur

LR parsers are used to parse the large class of context free grammars. This technique is called LR(k) parsing.

by Dinesh Thakur

Top-Down Parsing


Top-down parsing constructs parse tree for the input string, starting from root node and creating the nodes of parse tree in pre-order.

It is done by leftmost derivation for an input string.

by Dinesh Thakur

 • Parse tree is a hierarchical structure which represents the derivation of the grammar to yield input strings.

by Dinesh Thakur

Derivation is used to find whether the string belongs to a given grammar.

by Dinesh Thakur

Grammars are used to describe the syntax of a programming language. It specifies the structure of expression and statements.

stmt -> if (expr) then stmt

where stmt denotes statements,

expr denotes expressions.

by Dinesh Thakur

Syntax analysis is the second phase of compiler.

Syntax analysis is also known as parsing.

Parsing is the process of determining whether a string of tokens can be generated by a grammar.

It is performed by syntax analyzer which can also be termed as parser.

In addition to construction of the parse tree, syntax analysis also checks and reports syntax errors accurately.


                   C = a + b * 5

Syntax tree can be given as,

         Syntax analysis (parser)


Parser is a program that obtains tokens from lexical analyzer and constructs the parse tree which is passed to the next phase of compiler for further processing.

Parser implements context free grammar for performing error checks.

by Dinesh Thakur

• Lex is a tool in lexical analysis phase to recognize tokens using regular expression.

• Lex tool itself is a lex compiler.

by Dinesh Thakur

Regular expression is used to represent the language (lexeme) of finite automata (lexical analyzer).

by Dinesh Thakur

• Regular expressions are a notation to represent lexeme patterns for a token.

• They are used to represent the language for lexical analyzer.

• They assist in finding the type of token that accounts for a particular lexeme.

by Dinesh Thakur

• To ensure that a right lexeme is found, one or more characters have to be looked up beyond the next lexeme.

• Hence a two-buffer scheme is introduced to handle large lookaheads safely.

• Techniques for speeding up the process of lexical analyzer such as the use of sentinels to mark the buffer end have been adopted.

by Dinesh Thakur

Lexical analysis is the process of converting a sequence of characters from source program into a sequence of tokens.

A program which performs lexical analysis is termed as a lexical analyzer (lexer), tokenizer or scanner.

Lexical analysis consists of two stages of processing which are as follows:

by Dinesh Thakur

Some commonly used compiler-construction tools. include

1. Parser generators.
2. Scanner generators.
3. Syntax-directed translation engines.
4. Automatic code generators.
5. Data-flow analysis engines.
6. Compiler-construction toolkits.

by Dinesh Thakur

The phases of a compiler can be grouped as:

by Dinesh Thakur

The structure of compiler consists of two parts:

Analysis part

• Analysis part breaks the source program into constituent pieces and imposes a grammatical structure on them which further uses this structure to create an intermediate representation of the source program.

• It is also termed as front end of compiler.

• Information about the source program is collected and stored in a data structure called symbol table.

by Dinesh Thakur

                     Language processing system

by Dinesh Thakur

A program written in high-level language is called as source code. To convert the source code into machine code, translators are needed.

A translator takes a program written in source language as input and converts it into a program in target language as output.