Anna University Regulation 2013 Information Technology (IT) CS6660 CD Notes for all 5 units are provided below. Download link for IT 6th SEM CS6660 Compiler Design Lecture Notes are listed down for students to make perfect utilization and score maximum marks with our study materials.

SYNTAX ANALYSIS

3.1 ROLE OF THE PARSER

Parser obtains a string of tokens from the lexical analyzer and verifies that it can be generated by the language for the source program. The parser should report any syntax errors in an intelligible fashion. The two types of parsers employed are:

1.Top down parser: which build parse trees from top(root) to bottom(leaves)

2.Bottom up parser: which build parse trees from leaves and work up the root.

Therefore there are two types of parsing methods– top-down parsing and bottom-up parsing

3.2 TOP-DOWN PARSING

A program that performs syntax analysis is called a parser. A syntax analyzer takes tokens as input and output error message if the program syntax is wrong. The parser uses symbol-lookahead and an approach called top-down parsing without backtracking. Top-downparsers check to see if a string can be generated by a grammar by creating a parse tree starting from the initial symbol and working down. Bottom-up parsers, however, check to see a string can be generated from a grammar by creating a parse tree from the leaves, and working up. Early parser generators such as YACC creates bottom-up parsers whereas many of Java parser generators such as JavaCC create top-down parsers.

3.3RECURSIVE DESCENT PARSING

Typically, top-down parsers are implemented as a set of recursive functions that descent through a parse tree for a string. This approach is known as recursive descent parsing, also known as LL(k) parsing where the first L stands for left-to-right, the second L stands for leftmost-derivation, and k indicates k-symbol lookahead. Therefore, a parser using the single symbol look-ahead method and top-down parsing without backtracking is called LL(1) parser. In the following sections, we will also use an extended BNF notation in which some regulation expression operators are to be incorporated.

A syntax expression defines sentences of the form , or . A syntax of the form defines sentences that consist of a sentence of the form followed by a sentence of the form followed by a sentence of the form . A syntax of the form defines zero or one occurrence of the form . A syntax of the form defines zero or more occurrences of the form .

A usual implementation of an LL(1) parser is:

initialize its data structures,

get the lookahead token by calling scanner routines,

and call the routine that implements the start symbol.

Here is an example.

proc syntaxAnalysis()

begin

initialize(); // initialize global data and structures

nextToken(); // get the lookahead token

program(); // parser routine that implements the start symbol

end;

3.4 FIRST AND FOLLOW

To compute FIRST(X) for all grammar symbols X, apply the following rules until no more terminals or e can be added to any FIRST set.

1. If X is terminal, then FIRST(X) is {X}.

2. If X->e is a production, then add e to FIRST(X).

3. If X is nonterminal and X->Y1Y2…Yk is a production, then place a in FIRST(X) if for some i, a is in FIRST(Yi) and e is in all of FIRST(Y1),…,FIRST(Yi-1) that is,

Y1…….Yi-1=*>e. If e is in FIRST(Yj) for all j=1,2,…,k, then add e to FIRST(X). For example, everything in FIRST(Yj) is surely in FIRST(X). If y1 does not derive e, then we add nothing more to FIRST(X), but if Y1=*>e, then we add FIRST(Y2) and so on.

To compute the FIRST(A) for all nonterminals A, apply the following rules until nothing can be added to any FOLLOW set.

1. Place $ in FOLLOW(S), where S is the start symbol and $ in the input right endmarker.

2. If there is a production A=>aBs where FIRST(s) except e is placed in FOLLOW(B).

3. If there is aproduction A->aB or a production A->aBs where FIRST(s) contains e, then everything in FOLLOW(A) is in FOLLOW(B).

Consider the following example to understand the concept of First and Follow.Find the first and follow of all non terminals in the Grammar

CS6660 CD Unit 1 notes **–**** ****Download Here**

CS6660 CD Unit 2 notes **–**** ****Download Here**

CS6660 CD Unit 3 notes **–**** ****Download Here**

CS6660 CD Unit 4 notes **–**** ****Download Here**

CS6660 CD Unit 5 notes **–**** ****Download Here**

If you require any other notes/study materials, you can comment in the below section.

__Related Links__

For CS6660 CD Previous Year Question Papers – **Click here**

For CS6660 CD Question Bank/2marks 16marks with answers – **Click here**

For CS6660 CD Important Questions/Answer Key – **Click here**

__Search Terms__

Anna University 6th SEM IT CD Lecture Notes

CS6660 Compiler Design Notes free download

Anna University IT CD Notes Regulation 2013

CS6660 Notes, CD Unit wise Lecture Notes – IT 6th Semester