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