Chapter 4
Lexical and Syntax Analysis

Introduction (From Addison-Wesley)
Lexical Analysis (From Addison-Wesley)

Example 0:
Click here to get a simple example.

Example 1:

Write a recursive descent parser for the following grammar.

<S> --->  <A> <B> <C>
<A> --->  a <A> | a
<B> --->  b <B> | b
<C> --->  c <C> | c

Non-terminals are in "< >" brackets, while lower case characters are terminals.

Your program should allow the user to input a statement, and check whether the statement is a valid statement in the grammar. Check your data as

1.   abc
2.   aabbbc
3.   bbaaaaac
4.   abbcccccc
Describe, in English, the above grammar.

Click to see the C++ program for this example.

Example 2:

Write a recursive descent parser for the following grammar.

<S> --->  <A> a <B> b
<A> --->  <A> b | b
<B> --->  a <B> | a

Non-terminals are in "< >" brackets, while lower case characters and numbers are terminals.

Your program should allow the user to input a statement, and check whether the statement is a valid statement in the grammar. Check your data as

1.   baab
2.   bbbab
3.   bbaaaaa
4.   bbaab
Check your data as
 
valid invalid
baab bbaab bbaaaab bbaaaaa bbab bab
bbbbaab bbaaab bbbaaab bbbb aab baa
baaab baaaaab bbbbbaab aaaa baabc b

Click to see the C++ program for this example.

Example 3:

Write a recursive descent parser for the following grammar.

<S> --->  a <S> c <B> | <A> | b
<A> --->  c <A> |  c
<B> --->  d | <A>

Non-terminals are in "< >" brackets, while lower case characters and numbers are terminals.

Your program should allow the user to input a statement, and check whether the statement is a valid statement in the grammar.
Check your data as

1.   abcd
2.   acccbd
3.   acccbcc
4.   acd
5.   accc
Sample data:
 
valid invalid
abcd abcc abcccc ab abc abcdcc
accd accc acccccc acd acccb abccd
acccccd ccccc b acccdc accb cccd
Click here to see the C++ program for this example.

Example 4. Write a recursive descent parser for the following grammar.

<assign> ---> <id> := <expr>
<id>     ---> A | B | C
<expr>   ---> <expr> + <term> | <term>
<term>   ---> <term> * <factor> | <factor>
<factor> ---> ( <expr> ) | <id>

Non-terminals are in "< >" brackets, while lower case characters and numbers are terminals.

Your program should allow the user to input a statement,
and check whether the statement is a valid statement in the grammar.
Check your data as
 
valid invalid
A:=B D:=B+C+A
C:=B+A A=B+C
B:=B+C+A A:C+A
A:=B*C A+B:=B
B:=B*C+A A+B=C
C:=(B+C)*A  
A:=B*(C+A)  
C:=B*B+A*A  
A:=A+B*C+B+C*(A+B)