Lexical and Syntax Analysis

Written on 19.08 by Unknown

We meet yet again through my blog and this time I'm gonna talk about my fourth assignment from Mr. Tri Djoko Wahjono, Ir, M.Sc. It is about " Lexical and Syntax Analysis", the fourth chapter from Sebesta's Programming Language Concepts book, so i answered 5 questions from the review questions and 5 questions from the problem sets. So here is my answer for them :


Review Question Answers
  1. What are three reason why syntax analyser are based on grammars?
  • Firstly grammars are clear and concise,the next reason is that the grammar description can be use as a direct basis for  the  analyzer and last grammar are modular or easy to maintain.
  1. Explain the three reason why lexical analysis is separated from syntax analysis
  • Simplicity: Techniques for lexical analysis are less complex than those required for syntax analysis.
  • Efficiency: although it pays to optimize the lexical analyzer, because lexical analysis requires a significant portion of total compilation time.
  • Portability: because the lexical analyzer reads input program files and often includes buffering of that input, it is somewhat platform dependent.
  1. Define lexeme and token.
  • Lexeme is the logical groupings that the lexical analyzer collects characters into
  • Token is the internal codes for categories of these groupings.
  1. What are the primary task of lexical analyser?
  • The primary tasks of a lexical analyzer is to performs syntax analysis at the lowest level of program structure.
  1. Describe briefly the three approaches to building a lexical analyser.
  • Write a formal description of the token patterns of the language using a descriptive language related to regular expression.
  •  Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
  • Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
Problem Set Answers
  1. Perform the pairwise disjointness test for the following grammar rules.
A. A → aB | b | cBB
FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test.

B. B → aB | bA | aBb
FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test.

C. A → aaA | b | caB
 FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test.

  1. Perform the pairwise disjointness test for the following grammar rules.
A. S → aSB | bAA
 FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test.

B. A → b[aB] | a
 FIRST(b{aB}) = {b}, FIRST (a) = {a}, passes the test.

C. B → aB | a
 FIRST(aB) = {a}, FIRST(a) = {a}, Fails the test.

  1. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c
a + b * c
Call lex /* returns a */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns + */
Exit <factor>
Exit <term>
Call lex /* returns b */
Enter <term>
Enter <factor>
Call lex /* returns * */
Exit <factor>
Call lex /* returns c */
Enter <factor>
Call lex /* returns end-of-input */
Exit <factor>
Exit <term>
Exit <expr>

  1. . Show a trace of the recursive descent parser given in Section 4.4.1 for the string a * (b + c)
a * (b + c)
Call lex /* returns a */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns * */
Exit <factor>
Call lex /* return (*/
Enter <factor>
Call lex /* returns b */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns + */
Exit <factor>
Exit <term>
Call lex /* returns c */
Enter <factor>
Exit <term>
Call lex / *return )*/
Exit <factor>
Exit <term>
Exit <expr>
Call lex /* returns end-of-input */
Exit <factor>
Exit <term>
Exit <expr>

  1. Given the following grammar and the right sentential form, draw a parse tree and show the phrases and simple phrases, as well as the handle. S – > aAb | bBA A-> ab|aAB B->aB|b
A. aaAbb
parse tree =
                     S
                  / | \
                 a  A  b
                    /|\
                  a A B
                         |
                         b
Handles = b, aAB
Phrases = aaAbb, aaABb, aAb
Simple Phrase = b

B. bBab
parse tree =
              S
          /   |  \
         b  B  A
                 / \
                 a b
Handles = ab
Phrases = bBab, bBA
Simple phrase = ab

C. aaAbBb
aaAbBb = aSBb = aSBB = x
therefore the last string cannot be derived from given grammar.

Posted in , , ,

If you enjoyed this post Subscribe to our feed

No Comment

Posting Komentar