1
$\begingroup$

I have this Grammar below:

Expr ::= Term "(" Term ")"

Term ::= Ident | "(" Expr ")"

Start symbol: <Expr>
Terminal symbol: Ident ::= [a-z]+

And I wonder if it is possible to construct a recursive descent parser for grammar G2?

I think this won't be able to do that?

$\endgroup$
1
  • 2
    $\begingroup$ Why do you think that? (And what us your question? "Am I right?" questions don't really fit well here.) $\endgroup$
    – rici
    May 9, 2021 at 20:45

1 Answer 1

2
$\begingroup$

You will be able to.

Consider what happens when you try parsing a string as an Expr: you will need to read a term. If your term is starts with an english alphabet character, then its an Ident and once you stop seeing letters a-z, then you have finished reading Term. If it does not start with an alphabet character, then you need to see a '(' and you will retry reading an expression from there (by induction this will work), and finally read a ')'.

So we can successfully read the first Term, and after that we just need to see a '(', another Term (and again by induction we can do that) and finally a ')'

This language has no ambiguity so its pretty easy to parse.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.