Understanding Syntax Analysis in Compiler

In this class, We discuss Understanding Syntax Analysis in Compiler.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of lexical analysis. Click Here.

The reader should have a basic understanding of context-free grammar. Click Here.

First, We refresh the concept of context-free grammar. Then we go to the syntax analysis phase.

Example:

The below example is context-free grammar.

S – aSb | ab

The below example shows how context-free grammar is expanded.

We start from expanding S.

We check the input symbol a and expand S.

The variable ‘S’ is non-terminal.

After completion of the expansion of S, we check for input symbol b.

the context-free grammar is used in the syntax analysis phase.

Example:

First, we understand simple examples and discuss a complex examples.

The below example is a line showing the ‘if’ statement in a programming language.

The ‘if’ statement is divided into tokens in the lexical analysis phase.

‘a’ is an identifier token.

‘(‘is a symbol token.

‘< ‘is a relational operator token.

We use the tokens as input to the syntax analysis phase.

In the syntax analysis phase, we check the given statement is syntactically correct or not.

In our example. after finding the ‘if’ token, we need to have ‘(‘token.

After the ‘(‘ token, we need an expression.

We say it is syntactically correct if everything is identified according to the ‘if’ statement.

The below example shows the context-free grammar for finding the ‘if statement.

Small letters are terminal symbols.

S – if ( EXPR ) than

EXPR – id + id | id < id

The below diagram shows the expansion of the ‘if’ statement.

The EXPR production identifies only two expressions.

Usually, we need to write context-free grammar to identify all the expressions in our programming language.

In our next class, we will discuss expression grammar.

Assume if the open bracket is missing in the ‘if’ statement.

During the expansion, we can easily identify the missing syntax and error is identified.

Example 2:

with this example, a deeper understanding of the syntax analysis phase.

The below program is from pascal language.

The program starts with begin in pascal language and is complete with the ‘end.’

In between the begin and end, we write the statements.

We are writing context-free grammar for easy understanding to find only four statements.

1) assignment statement

2) while loop statement

3) if statement

4) the print statement

The below example shows the context-free grammar for finding the four statements.

Similarly, we write context-free grammar to identify all the statements in our programming language.

Take the example i:= 1 and i:= i-1.

The assignment statements in our language are taking expression and constants.

The production to identify expressions should take constants and expressions.

Similarly, while a statement is given while expressions do

After ‘do’, we can have statements and finally end keyword.

The first production COMPSTMT – begin STMT end.

The first production is compound statement is checking for begin and end, in between expanding statement.

The STMT production is identifying four statements. So we have four productions.

We can write any number of statements in between begin and end.

STMT – P will identify the print statement

We need to write production ‘P’ to identify the print statements.

STMT – id:= EXPR will identify assignment statements.

Similarly remaining two productions identify the while loop and if statement.

To repeat the STMT, we add one more production STMT – STMT STMT

The below diagram shows how the entire program syntax analysis is made.