Compiler Design and Construction - Unit Wise Questions

A compiler operates in phases. A phase is a logically interrelated operation that takes source program in one representation and produces output in another representation. The phases of a compiler are shown in below:

1. Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

2. Synthesis phase construct the desired target program from the intermediate representation. The synthesis part of compiler consists of the following phases: Intermediate code generation, Code optimization and Target code generation.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

Example:

    Input String: c = a + b * 3

    Tokens: id1 = id2 + id3 * 3

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

Example:

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example:

4. Intermediate Code Generation:

If the program syntactically and semantically correct then intermediate code generator generates a simple machine independent intermediate language. The intermediate code should be generated in such a way that it can easily translated into the target machine code.

Example:

    t1 = 3.0;

    t2 = id3 * t1;

    t3 = id2 + t2;

    id1 = t3;

5. Code Optimization:

It is used to improve the intermediate code so that the output of the program could run faster and takes less space. It removes the unnecessary lines of the code and arranges the sequence of statements in order to speed up the program execution without wasting resources.

Example:

    t2 = id3 * 3.0;

    id1 = id2 + t2;

6. Code Generation:

Code generation is the final stage of the compilation process. It takes the optimized intermediate code as input and maps it to the target machine language.

Example:

    MOV  R1, id3

    MUL  R1, #3.0

    MOV  R2, id2

    ADD  R1, R2

    MOV  id1, R1

Symbol Table

Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the  analysis phase of compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its type, its position in storage, and any other relevant information.

Error Handling

Whenever an error is encountered during the compilation of the source program, an error handler is invoked. Error handler generates a suitable error reporting message regarding the error encountered.

A compiler is a program that takes a program written in a source language and translates it into an equivalent program in a target language. As an important part of a compiler is error showing to the programmer.

Block diagram for phases of compiler:

Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example of Analysis phase:

Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

Block diagram for phases of compiler:

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example of Analysis phase:

A compiler operates in phases. A phase is a logically interrelated operation that takes source program in one representation and produces output in another representation. The phases of a compiler are shown in below:

1. Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

2. Synthesis phase construct the desired target program from the intermediate representation. The synthesis part of compiler consists of the following phases: Intermediate code generation, Code optimization and Target code generation.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

Example:

    Input String: c = a + b * 3

    Tokens: id1 = id2 + id3 * 3

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

Example:

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example:

4. Intermediate Code Generation:

If the program syntactically and semantically correct then intermediate code generator generates a simple machine independent intermediate language. The intermediate code should be generated in such a way that it can easily translated into the target machine code.

Example:

    t1 = 3.0;

    t2 = id3 * t1;

    t3 = id2 + t2;

    id1 = t3;

5. Code Optimization:

It is used to improve the intermediate code so that the output of the program could run faster and takes less space. It removes the unnecessary lines of the code and arranges the sequence of statements in order to speed up the program execution without wasting resources.

Example:

    t2 = id3 * 3.0;

    id1 = id2 + t2;

6. Code Generation:

Code generation is the final stage of the compilation process. It takes the optimized intermediate code as input and maps it to the target machine language.

Example:

    MOV  R1, id3

    MUL  R1, #3.0

    MOV  R2, id2

    ADD  R1, R2

    MOV  id1, R1

Symbol Table

Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the  analysis phase of compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its type, its position in storage, and any other relevant information.

Error Handling

Whenever an error is encountered during the compilation of the source program, an error handler is invoked. Error handler generates a suitable error reporting message regarding the error encountered.

A compiler is a program that takes a program written in a source language and translates it into an equivalent program in a target language. As an important part of a compiler is error showing to the programmer.

A compiler operates in phases. A phase is a logically interrelated operation that takes source program in one representation and produces output in another representation. The phases of a compiler are shown in below:

1. Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

2. Synthesis phase construct the desired target program from the intermediate representation. The synthesis part of compiler consists of the following phases: Intermediate code generation, Code optimization and Target code generation.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

Example:

    Input String: c = a + b * 3

    Tokens: id1 = id2 + id3 * 3

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

Example:

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example:

4. Intermediate Code Generation:

If the program syntactically and semantically correct then intermediate code generator generates a simple machine independent intermediate language. The intermediate code should be generated in such a way that it can easily translated into the target machine code.

Example:

    t1 = 3.0;

    t2 = id3 * t1;

    t3 = id2 + t2;

    id1 = t3;

5. Code Optimization:

It is used to improve the intermediate code so that the output of the program could run faster and takes less space. It removes the unnecessary lines of the code and arranges the sequence of statements in order to speed up the program execution without wasting resources.

Example:

    t2 = id3 * 3.0;

    id1 = id2 + t2;

6. Code Generation:

Code generation is the final stage of the compilation process. It takes the optimized intermediate code as input and maps it to the target machine language.

Example:

    MOV  R1, id3

    MUL  R1, #3.0

    MOV  R2, id2

    ADD  R1, R2

    MOV  id1, R1

Symbol Table

Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the  analysis phase of compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its type, its position in storage, and any other relevant information.

Error Handling

Whenever an error is encountered during the compilation of the source program, an error handler is invoked. Error handler generates a suitable error reporting message regarding the error encountered.

A compiler operates in phases. A phase is a logically interrelated operation that takes source program in one representation and produces output in another representation. The phases of a compiler are shown in below:

1. Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

2. Synthesis phase construct the desired target program from the intermediate representation. The synthesis part of compiler consists of the following phases: Intermediate code generation, Code optimization and Target code generation.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

Example:

    Input String: c = a + b * 3

    Tokens: id1 = id2 + id3 * 3

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

Example:

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example:

4. Intermediate Code Generation:

If the program syntactically and semantically correct then intermediate code generator generates a simple machine independent intermediate language. The intermediate code should be generated in such a way that it can easily translated into the target machine code.

Example:

    t1 = 3.0;

    t2 = id3 * t1;

    t3 = id2 + t2;

    id1 = t3;

5. Code Optimization:

It is used to improve the intermediate code so that the output of the program could run faster and takes less space. It removes the unnecessary lines of the code and arranges the sequence of statements in order to speed up the program execution without wasting resources.

Example:

    t2 = id3 * 3.0;

    id1 = id2 + t2;

6. Code Generation:

Code generation is the final stage of the compilation process. It takes the optimized intermediate code as input and maps it to the target machine language.

Example:

    MOV  R1, id3

    MUL  R1, #3.0

    MOV  R2, id2

    ADD  R1, R2

    MOV  id1, R1

Symbol Table

Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the  analysis phase of compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its type, its position in storage, and any other relevant information.

Error Handling

Whenever an error is encountered during the compilation of the source program, an error handler is invoked. Error handler generates a suitable error reporting message regarding the error encountered.

Difference between Interpreter and Compiler

Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the analysis phase of a compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its type, its position in storage, and any other relevant information.

Symbol tables typically need to support multiple declarations of the same identifier within a program. The lexical analyzer can create a symbol table entry and can return token to the parser, say id, along with a pointer to the lexeme. Then the parser can decide whether to use a previously created symbol table or create new one for the identifier.

The basic operations defined on a symbol table include

• allocate – to allocate a new empty symbol table
• free – to remove all entries and free the storage of a symbol table
• insert – to insert a name in a symbol table and return a pointer to its entry
• lookup – to search for a name and return a pointer to its entry
• set_attribute – to associate an attribute with a given entry
• get_attribute – to get an attribute associated with a given entry

A compiler is a program that takes a program written in a source language and translates it into an equivalent program in a target language. As an important part of a compiler is error showing to the programmer.

Block diagram for phases of compiler:

Synthesis phase construct the desired target program from the intermediate representation. The synthesis part of compiler consists of the following phases: Intermediate code generation, Code optimization and Target code generation.

1. Intermediate Code Generation:

If the program syntactically and semantically correct then intermediate code generator generates a simple machine independent intermediate language. The intermediate code should be generated in such a way that it can easily translated into the target machine code.

Example:

Intermediate code for: id1 = id2 + id3 * 3.0

    t1 = 3.0;

    t2 = id3 * t1;

    t3 = id2 + t2;

    id1 = t3;

2. Code Optimization:

It is used to improve the intermediate code so that the output of the program could run faster and takes less space. It removes the unnecessary lines of the code and arranges the sequence of statements in order to speed up the program execution without wasting resources.

Example:

    t2 = id3 * 3.0;

    id1 = id2 + t2;

3. Code Generation:

Code generation is the final stage of the compilation process. It takes the optimized intermediate code as input and maps it to the target machine language.

Example:

    MOV  R1, id3

    MUL  R1, #3.0

    MOV  R2, id2

    ADD  R1, R2

    MOV  id1, R1

A compiler is a program that takes a program written in a source language and translates it into an equivalent program in a target language. As an important part of a compiler is error showing to the programmer.

Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example of Analysis phase:

For the construction of a compiler, the compiler writer uses different types of software tools that are known as compiler construction tools. These tools make use of specialized languages for specifying and implementing specific components, and most of them use sophisticated algorithms. The tools should hide the details of the algorithm used and produce component in such a way that they can be easily integrated into the rest of the compiler. Some of the most commonly used compiler construction tools are:

1. Parser generators: They automatically produce syntax analyzers from a grammatical description of a programming language.

2. Scanner generators: They produce lexical analyzers from a regular-expression description of the tokens of a language.

3. Syntax-directed translation engine: They produce collections of routines for walking a parse tree and generating intermediate code.

4. Code-generator generators: They produce a code generator from a collection of rules for translating each operation of the intermediate language into the machine language for a target machine.

5. Data-flow analysis engines: They facilitate the gathering of information about how the data is transmitted from one part of the program to another. For code optimization, data-flow analysis is a key part.

6. Compiler-construction toolkits: They provide an integrated set of routines for constructing various phases of a compiler.

Error detection and reporting of errors are important functions of the compiler. Whenever an error is encountered during the compilation of the source program, an error handler is invoked. Error handler generates a suitable error reporting message regarding the error encountered. The error reporting message allows the programmer to find out the exact location of the error. Errors can be encountered at any phase of the compiler during compilation of the source program for several reasons such as:

• In lexical analysis phase, errors can occur due to misspelled tokens, unrecognized characters, etc. These errors are mostly the typing errors.
• In syntax analysis phase, errors can occur due to the syntactic violation of the language.
• In intermediate code generation phase, errors can occur due to incompatibility of operands type for an operator.
• In code optimization phase, errors can occur during the control flow analysis due to some unreachable statements.
• In code generation phase, errors can occurs due to the incompatibility with the computer architecture during the generation of machine code. For example, a constant created by compiler may be too large to fit in the word of the target machine.
• In symbol table, errors can occur during the bookkeeping routine, due to the multiple declaration of an identifier with ambiguous attributes.

After detecting an error, a phase must somehow deal with that error, so that compilation can proceed, allowing further errors in the source program to be detected.

Error handler contains a set of routines for handling error encountered in any phase of the compiler. Every phase of compiler will call an appropriate routine of the error handler as per their specifications.

Error detection and reporting of errors are important functions of the compiler. Whenever an error is encountered during the compilation of the source program, an error handler is invoked. Error handler generates a suitable error reporting message regarding the error encountered. The error reporting message allows the programmer to find out the exact location of the error. Errors can be encountered at any phase of the compiler during compilation of the source program for several reasons such as:

• In lexical analysis phase, errors can occur due to misspelled tokens, unrecognized characters, etc. These errors are mostly the typing errors.
• In syntax analysis phase, errors can occur due to the syntactic violation of the language.
• In intermediate code generation phase, errors can occur due to incompatibility of operands type for an operator.
• In code optimization phase, errors can occur during the control flow analysis due to some unreachable statements.
• In code generation phase, errors can occurs due to the incompatibility with the computer architecture during the generation of machine code. For example, a constant created by compiler may be too large to fit in the word of the target machine.
• In symbol table, errors can occur during the bookkeeping routine, due to the multiple declaration of an identifier with ambiguous attributes.

After detecting an error, a phase must somehow deal with that error, so that compilation can proceed, allowing further errors in the source program to be detected.

Error handler contains a set of routines for handling error encountered in any phase of the compiler. Every phase of compiler will call an appropriate routine of the error handler as per their specifications.

A compiler is a program that takes a program written in a source language and translates it into an equivalent program in a target language. As an important part of a compiler is error showing to the programmer.

Block diagram for phases of compiler:

In Semantic Analysis phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer. 

Semantic analyzer is required when the compiler may require performing some additional checks such as determining the type of expressions and checking that all statements are correct with respect to the typing rules, that variables have been properly declared before they are used, that functions are called with the proper number of parameters etc. This semantic analyzer phase is carried out using information from the parse tree and the symbol table.

Example:

Given RE;

(ε + 0)*10

The augmented RE of the given RE is:

(ε + 0)*10 #

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {1, 2}

followpos(2) = {3}

followpos(3) = {4}

Now,

1) Start state of DFA = firstpos(root) = {1, 2} = S₀

Use followpos of symbol representing position in RE to obtain the next state of DFA.

2) From S₀ = {1, 2}

    1  represents '0'

    2 represents '1'

followpos(1) = {1, 2} = S₀

     δ(s₀, 0) = S₀

followpos(2) = {3} = S₁

    δ(S₀, 1) = S₁

3) From S₁ = {3}

    Here 3 represents '0'

followpos(3) = {4} = S₂

     δ(S₁, 0) = S₂

4) From S₂ = {4}

    Here 4 represents '#'

Now there was no new states occur.

Therefore, Final state = {S₂}

Now the resulting DFA of given regular expression is:

Lexical Analyzer Generator (Lex/Flex) systematically translate regular definitions into C source code for efficient scanning. Generated code is easy to integrate in C applications. Flex is a latter version of lex.

• Firstly, specification of a lexical analyzer is prepared by creating a program lex.l in Lex/Flex
• lex.l is run into lex compiler to produce a C program lex.yy.c
• lex.yy.c consists of the tabular representation of lex.l, together with a standard routine that uses the table to recognize lexeme.
• Lex.yy.c is run through C compiler to produce the object program a.out which is a lexical analyzer that input into tokens.

A flex specification consists of three parts:

1. regular definitions, C declarations in %{ %}

        %%

2. translation rules

        %%

3. user-defined auxiliary procedures

The translation rules are of the form:

    p1     { action1 }

    p2     { action2 }

    …

    pn     { actionn }

Lex/flex regular definitions are of the form:

       name definition

E.g. Digit   [0-9]

Example of lex specification

%{

    #include <stdio.h>

%}

%%

[0-9]+   { printf(“%s\\n”, yytext); }

. | \\n     {  }

%%

main()

{ yylex();

}

Difference between top-down and bottom-up parsing methods

Now, 

Given grammar:

    1. S → aETe

    2. E → Ebc

    3. E → b

    4. T → d

The augmented grammar of given grammar is,

S‘ → S

S → aETe

E → Ebc

E → b

T → d

Next, we obtain the canonical collection of sets of LR(0) items, as follows,

I₀ = closure({S'→•S}) = {S'→•S, S→ •aETe }

goto(I₀, S) = {S'→S•}= I₁

goto(I₀, a) = closure({S→ a•ETe}) = {S→ a•ETe, E → •Ebc, E → •b}= I₂

goto(I₂, E) =  closure({S→ aE•Te, E → E•bc}) = {S→ aE•Te, E → E•bc, T → •d}= I₃

goto(I₂, b) =  closure({E → b•}) = {E → b•} = I₄

goto(I₃ , d) = closure({T → d•}) = I₅

goto(I₃ , b) = closure({E → Eb•c}) = {E → Eb•c}= I₆

goto(I₃ , T) = closure({S→ aET•e}) = {S→ aET•e} = I₇

goto( I₆ , c) = closure({E → Ebc•}) = {E → Ebc•}= I₈

goto(I₇ , e) = closure({S→ aETe•}) = {S→ aETe•}= I₉

FOLLOW set for non-terminals are,

FOLLOW(S) = {$}

FOLLOW(E) = {b, d}

FOLLOW(T) = {e}

Now, the SLR parsing table is,

The lexical analyzer needs to scan and identify only a finite set of valid string/token/lexeme that belong to the language in hand. It searches for the pattern defined by the language rules.

Regular expressions have the capability to express finite languages by defining a pattern for finite strings of symbols. The grammar defined by regular expressions is known as regular grammar. The language defined by regular grammar is known as regular language.

An important notation for specifying the patterns in known as Regular expression. Set of strings is matched by each pattern and the names of the set of strings are served by the regular expressions. Regular languages describe the programming language tokens. 

The various operations on languages are:

• Union of two languages L and M is written as

            L U M = {s | s is in L or s is in M}

• Concatenation of two languages L and M is written as

            LM = {st | s is in L and t is in M}

• The Kleene Closure of a language L is written as

            L* = Zero or more occurrence of language L.

Representing valid tokens of a language in regular expression:

If x is a regular expression, then:

• x* means zero or more occurrence of x.
• x⁺ means one or more occurrence of x.
• x? means at most one occurrence of x
• [a-z] is all lower-case alphabets of English language.
• [A-Z] is all upper-case alphabets of English language.
• [0-9] is all natural digits used in mathematics.

Representing occurrence of symbols using regular expressions:

• letter = [a – z] or [A – Z]
• digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 or [0-9]
• sign = [ + | - ]

Representing language tokens using regular expressions:

• Decimal = (sign)?(digit)+
• Identifier = (letter)(letter | digit)*

Lexical Analyzer reads the input characters of the source program, groups them into lexemes, and produces a sequence of tokens for each lexeme. The tokens are then sent to the parser for syntax analysis.

Responsibilities of a lexical analyzer are:

• It reads the input character and produces output sequence of tokens that the Parser uses for syntax analysis.
• Lexical analyzer helps to identify token into the symbol table.
• Lexical Analyzer is also responsible for eliminating comments and white spaces from the source program.
• It also generates lexical errors.
• Lexical analyzer is used by web browsers to format and display a web page with the help of parsed data from JavsScript, HTML, CSS

Second part:

/* Lex program to recognize the identifier of C language */

Lexical Analyzer Generator (Lex/Flex) systematically translate regular definitions into C source code for efficient scanning. Generated code is easy to integrate in C applications. Flex is a latter version of lex.

• Firstly, specification of a lexical analyzer is prepared by creating a program lex.l in Lex/Flex
• lex.l is run into lex compiler to produce a C program lex.yy.c
• lex.yy.c consists of the tabular representation of lex.l, together with a standard routine that uses the table to recognize lexeme.
• Lex.yy.c is run through C compiler to produce the object program a.out which is a lexical analyzer that input into tokens.

A flex specification consists of three parts:

1. regular definitions, C declarations in %{ %}

        %%

2. translation rules

        %%

3. user-defined auxiliary procedures

The translation rules are of the form:

    p1     { action1 }

    p2     { action2 }

    …

    pn     { actionn }

Lex/flex regular definitions are of the form:

       name definition

E.g. Digit   [0-9]

Example of lex specification

%{

    #include <stdio.h>

%}

%%

[0-9]+   { printf(“%s\\n”, yytext); }

. | \\n     {  }

%%

main()

{ yylex();

}

Token

Token is a sequence of characters that can be treated as a single logical entity. For example, Identifiers, Keywords, Operators, Constants etc.

Pattern

A set of string in the input for which the same token is produced as output. This set of string is described by a rule called a pattern associated with the token. For example, “a letter followed by zero or more letters, digits, or underscores.”

Lexeme

A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. 

Input Buffering

Lexical analysis needs to look ahead several characters before a match can be announced. We have two buffer input scheme that is useful when look ahead is necessary.

• Buffer Pair
• Sentinels

Buffer Pair (2N Buffering):

In this technique buffer is divided into two halves with N-characters each, where N is number of characters on the disk block like 1024 and 4096. Rather than reading characters by characters from file we read N input character at once. If there are fewer than N character in input EOF marker is placed. There are two pointers: lexeme pointer and forward pointer.

Lexeme pointer points to the start of the lexeme while forward pointer scans the input buffer for lexeme. When forward pointer reaches the end of one half, second half is loaded and forwarded pointer points to the beginning of the next half.

Sentinels:

While using buffer pair technique, we have to check each time fwd is moved that it doesn't crosses the buffer half and when it reaches end of buffer, the other one needs to be loaded. We can solve this problem by introducing a sentinel character at the end of both halves of buffer. The sentinel can be any character which is not a part of source program. EOF is usually preferred as it will also indicate end of source program. It signals the need for some special action (fill other buffer-half, or terminate processing).

The lexical analyzer needs to scan and identify only a finite set of valid string/token/lexeme that belong to the language in hand. It searches for the pattern defined by the language rules. Regular expressions have the capability to express finite languages by defining a pattern for finite strings of symbols. So regular expressions are used in token specification.

Regular expressions are the algebraic expressions that are used to describe tokens of a programming language. It uses the three regular operations. These are called union/or, concatenation and star. Brackets ( and ) are used for grouping.

• Union of two languages L and M is written as

                L U M = {s | s is in L or s is in M}

• Concatenation of two languages L and M is written as

                LM = {st | s is in L and t is in M}

• The Kleene Closure of a language L is written as

                L* = Zero or more occurrence of language L.

Now,

In C the regular expression for identifiers can be written using the regular definition as;

    letter → A | B | .... | Z | a | b | .... | z | _

    digit → 0 | 1 | 2 | ..... |9

    identifier → letter(letter | digit)*

The regular expression representing identifiers without using regular definition:

(A | B | C |.........| Z | a | b | c |.........| z | _). ((A | B | C |.........| Z | a | b | c |.........| z | _ |) (1 | 2 |................| 9))*

Given RE;

(a+b)*ab

The augmented RE of the given RE is:

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {1, 2, 3}

followpos(2) = {1, 2, 3}

followpos(3) = {4}

followpos(4) = {5}

Now,

1) Start state of DFA = firstpos(root) = {1, 2, 3} = S₀

Use followpos of symbol representing position in RE to obtain the next state of DFA.

2) From S₀ = {1, 2, 3}

    1 and 3 represents 'a'

    2 represents 'b'

followpos({1, 3}) = {1, 2, 3, 4} = S₁

    δ(s₀, a) = S₁

followpos({2}) = {1, 2, 3} = S₀

    δ(S₀, b) = S₀

3) From S₁ = {1, 2, 3, 4}

    1, 3 → a

    2, 4 → b

followpos({1, 3}) = {1, 2, 3, 4} = S₁

     δ(S₁, a) = S₁

followpos({2, 4}) = {1, 2, 3, 5} = S₂

     δ(S₁, b) = S₂

4) From S₂ = {1, 2, 3, 5}

    1, 3 → a

    2 → b

    5 → #

followpos({1, 3}) = {1, 2, 3, 4}= S₁

    δ(S₂, a) = S₁

followpos({2}) = {1, 2, 3} = S₀

     δ(S₂, b) = S₀

Now there was no new states occur.

Therefore, Final state = {S₂}

Now the resulting DFA of given regular expression is:

In lexical analysis phase, Lexical Analyzer reads the input characters of the source program, groups them into lexemes, and produces a sequence of tokens for each lexeme. The tokens are then sent to the parser for syntax analysis.

Task carried out in lexical analysis phase are:

• Lexical analyzer reads the input character and produces output sequence of tokens that the Parser uses for syntax analysis.
• Lexical analyzer helps to identify token into the symbol table.
• Lexical Analyzer is also responsible for eliminating comments and white spaces from the source program.
• It also generates lexical errors.
• Lexical analyzer is used by web browsers to format and display a web page with the help of parsed data from JavsScript, HTML, CSS

Second part:

Using the subset construction we have the DFA as:

Now Transition diagram for above table is:

The process of reducing the given input string into the starting symbol is called shift-reducing parsing.

A shift reduce parser uses a stack to hold the grammar symbol and an input buffer to hold the input string W. 

Sift reduce parsing performs the two actions: shift and reduce.

• At the shift action, the current symbol in the input string is pushed to a stack.
• At each reduction, the symbols will replaced by the non-terminals. The symbol is the right side of the production and non-terminal is the left side of the production.

Now,

Given grammar;

Input String: a*(a+a)

Shift reduce parsing action for given input string is shown below:

In static type checking, the type of variable is known at compile time (it checks the type of variable before running). Typical examples of static checking are:

    • Type checks: Report an error if an operator is applied to an incompatible operand.

    • Flow-of-control checks: Statements that results in a branch need to be terminated correctly.

    • Uniqueness checks: There are situations where an object must be defined exactly once.

    • Name-related checks: Sometimes the same names may be appeared two or more times.

In dynamic type checking, the type of variable is known at runtime (it checks the type of variable while executing). Compiler generates verification code to enforce programming language's dynamic semantics. If a programming language has no any dynamic checking, it is called strongly typed language i.e. there will be no type errors during run-time.

Now,

SDD to carry out type checking for the given expression is given below:

E → id     { E.type = lookup(id.entry) }

E → E1 op E2     { if (E1.type = integer and E2.type = integer) then E.type = integer

        else if (E1.type = integer and E2.type = real) then E.type = real

        else if (E1.type = real and E2.type = integer) then E.type = real

        else if (E1.type = real and E2.type = real) then E.type = real

        else E.type = type-error }

E → E1 relop E2    { if E1.type = boolean and E2.type = boolean then E.type = boolean

                    else E.type = error}

E → E1 [E2]     { if (E2.type = int and E1.type = array(s, t)) then E.type = t

                   else E.type = type-error }

E →E1 ↑    { if E1.type = pointer(t) then E.type = t

                else type-error}

The process of reducing the given input string into the starting symbol is called shift-reducing parsing.

A shift reduce parser uses a stack to hold the grammar symbol and an input buffer to hold the input string W. 

Sift reduce parsing performs the two actions: shift and reduce.

• At the shift action, the current symbol in the input string is pushed to a stack.
• At each reduction, the symbols will replaced by the non-terminals. The symbol is the right side of the production and non-terminal is the left side of the production.

Now,

Given grammar;

Input String: (x+x)*a

Shift reduce parsing action for given input string is shown below:

At $S*a parser can neither perform shift action nor reduce action. Hence, error occurred.

Lexical Analyzer Generator (Lex/Flex) systematically translate regular definitions into C source code for efficient scanning. Generated code is easy to integrate in C applications. Flex is a latter version of lex.

• Firstly, specification of a lexical analyzer is prepared by creating a program lex.l in Lex/Flex
• lex.l is run into lex compiler to produce a C program lex.yy.c
• lex.yy.c consists of the tabular representation of lex.l, together with a standard routine that uses the table to recognize lexeme.
• Lex.yy.c is run through C compiler to produce the object program a.out which is a lexical analyzer that input into tokens.

A  lex/flex specification consists of three parts:

1. regular definitions, C declarations in %{ %}

        %%

2. translation rules

        %%

3. user-defined auxiliary procedures

The translation rules are of the form:

    p1     { action1 }

    p2     { action2 }

    …

    pn     { actionn }

Lex/flex regular definitions are of the form:

       name definition

E.g. Digit   [0-9]

Example of lex specification

%{

    #include <stdio.h>

%}

%%

[0-9]+   { printf(“%s\\n”, yytext); }

. | \\n     {  }

%%

main()

{ yylex();

}

If  Σ is an alphabet of basic symbols, then a regular definition is a sequence of definition of the form

d₁ → r₁

d₂ → r₂

.....

d_n → r_n

where, d_i is a distinct name and r_i is a regular expression over symbols in  Σ ∪ {d₁, d₂, ...., d_i-1}

Now,

Regular definitions for the terminals used in given grammar are:

digit → [0-9]
num → digit+(. digit+)?(E[+|-]? digit+)?
letter → [A-Za-z]
id → letter ( letter | digit )*
if → if
then → then
else → else
relop → < | > | <= | >= | = | <>

Transition diagram for id:

Here 9, 10 & 11 are the name of states.

Transition diagram for num:

Difference between recursive descent and non-recursive predictive parsing

Now,

Given grammar;

Now, the FIRST and FOLLOW for the non-terminals are:

The given grammar is;

Now, the FIRST and FOLLOW of given non-terminals are:

FIRST(A) = FIRST(T) = FIRST(X) = {(, a}

FIRST(E) = {+, ∈}

FIRST(Y) = {*, ∈}

FOLLOW(A) = {), $}

FOLLOW(E) = {), $}

FOLLOW(T) = {), +, $}

FOLLOW(Y) = {), +, $}

FOLLOW(X) = {*, +, ), $}

Given RE;

(0 + 1)* 011

The augmented RE of the given RE is:

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {1, 2, 3}

followpos(2) = {1, 2, 3}

followpos(3) = {4}

followpos(4) = {5}

followpos(5) = {6}

Now,

1) Start state of DFA = firstpos(root) = {1, 2, 3} = S₀

Use followpos of symbol representing position in RE to obtain the next state of DFA.

2) From S₀ = {1, 2, 3}

    1 and 3 represents '0'

    2 represents '1'

followpos({1, 3}) = {1, 2, 3, 4} = S₁

    δ(s₀, 0) = S₁

followpos({2}) = {1, 2, 3} = S₀

    δ(S₀, 1) = S₀

3) From S₁ = {1, 2, 3, 4}

    1, 3 → 0

    2, 4 → 1

followpos({1, 3}) = {1, 2, 3, 4} = S₁

     δ(S₁, 0) = S₁

followpos({2, 4}) = {1, 2, 3, 5} = S₂

     δ(S₁, 1) = S₂

4) From S₂ = {1, 2, 3, 5}

    1, 3 → 0

    2, 5 → 1

followpos({1, 3}) = {1, 2, 3, 4}= S₁

    δ(S₂, 0) = S₁

followpos({2, 5}) = {1, 2, 3, 6} = S₃

     δ(S₂, 1) = S₃

5) From S₃ = {1, 2, 3, 6}

    1, 3 → 0

    2 → 1

    6 → #

followpos({1, 3}) = {1, 2, 3, 4}= S₁

    δ(S₃, 0) = S₁

followpos({2}) = {1, 2, 3} = S₀

    δ(S₃, 1) = S₀

Now there was no new states occur.

Therefore, Final state = {S₃}

Now the resulting DFA of given regular expression is:

Top-down parser is the parser which generates parse for the given input string with the help of grammar productions by expanding the non-terminals i.e. it starts from the start symbol and ends on the terminals.

Problems with top-down parsers are:

• Only judges grammatically
• Stops when it finds a single derivation.
• No semantic knowledge employed.
• No way to rank the derivations.
• Problems with left-recursive rules.
• Problems with ungrammatical sentences.

LR Parsing algorithm:

An LR parser comprises of a stack, an input buffer and a parsing table that has two parts: action and goto. Its stack comprises of entries of the form s_o X₁ s₁ X₂s₂ ... X_m s_m where every s_i is called a state and every X_i is a grammar symbol(terminal or non-terminal)

If top of the stack is S_m and input symbol is a, the LR parser consults action[s_m,a] which can be one of four actions.

1. Shift s , where s is a state.

2. Reduce using production A→ b

3. Accept

4. Error

The function goto takes a state and grammar symbol as arguments and produces a state.

The configuration of the LR parser is a tuple comprising of the stack contents and the contents of the unconsumed input buffer. It is of the form

(s_o X₁ s₁ X₂s₂ ... X_m s_m , a_i a_i+1 ... a_n $)

1. If action[s_m,a_i] = shift s, the parser executes a shift move entering the configuration

    (s_o X₁ s₁ X₂s₂ ... X_m s_ma_is , a_i+1 ... a_n $) shifting both a_i and the state s onto stack.

2. If action[s_m,a_i] = reduce A→ β , the parser executes a reduce move entering the configuration

    (s_o X₁ s₁ X₂s₂ ... X_m-r s_m-r As , a_i a_i+1 ... a_n $) . Here s = goto[s_m-r,A] and r is the length of handle β.

Note: if r is the length of β then the parser pops 2r symbols from the stack and push the state as on goto[s_m-r,A] . After reduction , the parser outputs the production used on reduce operation. A→β

3. If action[s_m,a_i] = Accept, then parser accept i.e. parsing successfully complete and stop.

4. If action[s_m,a_i] = error then call the error recovery routine.

Syntax tree for given arithmetic expression is shown below:

a*-(b+c) 

If a same terminal string can be derived from the grammar using two or more distinct left-most derivation (or right most) then the grammar is said to be ambiguous i.e. from an ambiguous grammar, we can get two or more distinct parse tree for the same terminal string.

For example:

E → E+E | E*E | id

String: id+id*id

Derivation 1:

Derivation 2:

For the string id + id * id, the above grammar generates two parse trees or two distinct derivation. So the grammar is ambiguous.

Given RE;

(a+∈) bc*

The augmented RE of the given RE is:

(a+∈) bc* #

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {2}

followpos(2) = {3, 4}

followpos(3) = {3, 4}

Now,

1) Start state of DFA = firstpos(root) = {1, 2} = S₀

Use followpos of symbol representing position in RE to obtain the next state of DFA.

2) From S₀ = {1, 2}

    1  represents 'a'

    2 represents 'b'

followpos(1) = {2} = S₁

     δ(s₀, a) = S₁

followpos(2) = {3, 4} = S₂

    δ(S₀, b) = S₂

3) From S₁ = {2}

    Here 2 represents 'b'

followpos(2) = {3, 4} = S₂

     δ(S₁, b) = S₂

4) From S₂ = {3, 4}

    Here 3 represents 'c'

    4 represents '#'

followpos(3) = {3, 4} = S₂

    δ(S₂, c) =  S₂

Now there was no new states occur.

Therefore, Final state = {S₂}

Now the resulting DFA of given regular expression is:

Difference between LR(0) and LR(1) algorithm

• LR(0)requires just the canonical items for the construction of a parsing table, but LR(1) requires the loookahead symbol as well.
• LR(1) allows us to choose the correct reductions and allows the use of grammar that are not uniquely invertible while LR(0) does not.
• LR(0) reduces at all items whereas LR(1) reduces only at lookahead symbols.
• LR(0) = canonical items and LR(1) = LR(0) + lookahead symbol.
• In canonical LR(0) collection, state/item is in the form:

        E.g. I₂ = { C → AB•}

        whereas In cannonical LR(1) collection, state/item is in the form: 

        E.g. I₂ = { C →d•, e/d} where e & d are lookahead symbol.

• Construction of canonical LR(0) collection starts with C = {closure({S‘→.S})} whereas Construction of canonical LR(1) collection starts with C = {closure({S‘→.S, $})} where S is the start symbol.
• LR(0) algorithm is simple than LR(1) algorithm.
• In LR(0), there may be conflict in parsing table while LL(1) parsing uses lookahead to avoid unnecessary conflicts in parsing table.

The augmented grammar of given grammar is:

S' → S

S → E

E → E+T | T

T → T*F | F

F → id

Next, we obtain the canonical collection of sets of LR(0) items, as follows,

A syntax analyzer or parser takes the input from a lexical analyzer in the form of token streams. The parser analyzes the source code (token stream) against the production rules to detect any errors in the code. The output of this phase is a parse tree.

The parser obtains a string of tokens from the lexical analyzer and verifies that the string can be generated by the grammar for the source language. It has to report any syntax errors if occurs.

The tasks of parser can be expressed as

• Analyzes the context free syntax
• Generates the parse tree
• Provides the mechanism for context sensitive analysis
• Determine the errors and tries to handle them

Algorithm for non-recursive predictive parsing:

1. Set ip to the first symbol of the input string.

2. Set the stack to $S where S is the start symbol of the grammar G.

3. Let X be the top stack symbol and ‘a’ be the symbol pointed by ip then

  Repeat

    a. If X is a terminal or ‘$’ then

        i. If X = a then pop X from the stack and advance ip

        ii. else error()

    b. Else

        If M[X,a] = Y₁Y₂Y₃....... Y_k then

            1. Pop X from Stack

            2. Push Y_k , Y_k-1, .....Y₂, Y₁ on the stack with Y₁ on top.

            3. Output the production X → Y₁Y₂Y₃....... Y_k

Until X = ‘$’.

Given grammar,

a) Removing left recursion of the given grammar;

    S → (L) | a

    L → SL'

    L' → ,SL' | ∈

b) Now, the FIRST and FOLLOW for the given symbols are:

A finite automaton is a mathematical (model) abstract machine that has a set of "state" and its "control" moves from state to state in response to external "inputs". The control may be either "deterministic" meaning that the automation can‘t be in more than one state at any one time, or "non-deterministic", meaning that it may be in several states at once. This distinguishes the class of automata as DFA or NFA.

• The DFA, i.e. Deterministic Finite Automata can‘t be in more than one state at any time.
• The NFA, i.e. Non-Deterministic Finite Automata can be in more than one state at a time.

Now,

DFA that will accept a string at zeros and ones that contains an odd number of zeros and an even number of ones is shown below:

Here,

Q = {q0, q1, q2, q3}

∑ = {0, 1}

δ = Above transition diagram

q0 = q0

F = {q2}

Given grammar;

Now, the FIRST and FOLLOW for the non-terminal symbols are:

Given grammar;

a) Leftmost derivation:

Since the above grammar produces two different left-most derivation for the sentence abab, the given grammar is ambiguous.

b) Rightmost derivation:

c) The corresponding parse tree for abab is

Recursive decent parsing is a top-down parsing technique that uses a set of recursive procedure to scan its input from left to right. It may involve backtracking. It starts from the root node (start symbol) and use the first production, match the input string against the production rules and if there is no match backtrack and apply another rule.

Rules:

1. Use two pointers iptr for pointing the input symbol to be read and optr for pointing the symbol of output string that is initially start symbol S.

2. If the symbol pointed by optr is non-terminal use the first production rule for expansion.

3. While the symbol pointed by iptr and optr is same increment the both pointers.

4. The loop at the above step terminates when

    a. A non-terminal is encountered in output 

    b. The end of input is reached. 

    c. Symbol pointed by iptr and optr is unmatched.

5. If 'a' is true, expand the non-terminal using the first rule and goto step 2

6. If 'b' is true, terminate with success

7. If 'c' is true, decrement both the pointers to the place of last non-terminal expansion and use the next production rule for non-terminal

8. If there is no more production and 'b' is not true report error.

Example:

Consider a grammar

S → cAd

A → ab | a

Input string is “cad”

Initially, iptr = optr = 0

The augmented grammar of given grammar is,

    C‘→ C

    C → AB

    A → a

    B → b

Next, we obtain the canonical collection of sets of LR(0) items, as follows,

I₀ = closure ({C‘ → •C}) = {C‘ → •C, C → •AB, A → •a}

goto(I₀, C) = closure(C‘ → C•) = { C‘ → C•} = I₁

goto(I₀, A) = closure(C → A•B) = { C → A•B, B → •b} = I₂

goto(I₀, a) = closure(A → a•) = { A → a• } = I₃

goto(I₂, B) = closure(C → AB•) = { C → AB•} = I₄

goto(I₂, b) = closure(B → b•) = { B → b•} = I₅

Now, the canonical collection of sets of LR(0) items for given grammar are:

The augmented grammar of given grammar is;

    E’→E

    E→E+T | T

    T→T*F | F

    F→ (E) | id

Next, we obtain the canonical collection of sets of LR(0) items, as follows,

I₀ = closure ({E‘ → •E})

    = {E‘ → •E, E → •E + T, E → •T, T → •T * F, T → •F, F → • (E), F → •id}

goto(I₀, E) = closure({E‘ → E•, E → E •+ T}) = {E‘ → E•, E → E •+ T} = I₁

goto(I₀, T) = closure({E → T•, T → T •* F}) = { E → T•, T → T •* F } = I₂

goto(I₀, F) = closure({T → F•}) = {T → F•} = I₃

goto(I₀, ( ) = closure({F → (•E)}) = {F → (•E), E → •E + T, E → •T, T → •T * F, T → •F, F → • (E), F → •id} = I₄

goto(I₀, id ) = closure({F → id•}) = {F → id•} = I₅

goto(I₁, + ) = closure({E → E + •T}) = {E → E +• T, T → •T * F, T → •F, F → • (E), F → •id} = I₆

goto(I₂, * ) = closure({T → T * •F}) = {T → T * •F, F → • (E), F → •id} = I₇

goto(I₄, E) = closure({F → (E•), E → E•+ T}) = {F → (E•), E → E•+ T } = I₈

goto(I₄, T) = closure({E → T•, T → T• * F}) = {E → T• , T → T•*F}= I₂

goto(I₄, F) = closure({T → F•}) = {T → F•} = I₃

goto(I₄, () = closure({F → •(E)} = I₄

goto(I₄, id) = closure({F → id•}) = I₅

goto(I₆, T) = closure({E → E +T•, T → T•* F}) = {E → E +T•, T → T•* F} = I₉

goto(I₆, F) = closure ({T→ F•}) = I₃

goto (I₆, () = closure ({F → (• E)} = I₄

goto(I₆, id) = closure({F → id•}) = I₅

goto(I₇, F ) = closure({T → T * F•})= {T → T * F•} = I₁₀

goto( I₇, () = closure({F → •(E)} = I₄

goto(I₇, id) = closure({F → id•}) = I₅

goto(I₈, ) ) = closure({F → (E) •}) = {F → (E) •} = I₁₁

goto(I₈, +) = closure({ E → E+•T} ) = I₆

goto(I₉, *) = closure({T → T*•F}) = { T → T*•F, F→ •(E), F→ •id } = I₇

Now,

The canonical collection of set of LR(0) items for given grammar are:

A syntax-directed definition (SDD) is a context-free grammar together with attributes and rules. Attributes are associated with grammar symbols and rules are associated with productions. For example,

Synthesized Attributes

The attribute of node that are derived from its children nodes are called synthesized attributes. Assume the following production:

    S → ABC

If S is taking values from its child nodes (A, B, C), then it is said to be a synthesized attribute, as the values of ABC are synthesized to S.

Example for synthesized attribute:

The Syntax Directed Definition associates to each non terminal a synthesized attribute called val.

In synthesized attributes, value owns from child to parent in the parse tree. For example, for string 3*2+5

Inherited Attributes

The attributes of node that are derived from its parent or sibling nodes are called inherited attributes. If the value of the attribute depends upon its parent or siblings then it is inherited attribute. As in the following production,

S → ABC

"A‟ can get values from S, B and C. B can take values from S, A, and C. Likewise, C can take values from S, A, and B.

Example for Inherited Attributes: