0
$\begingroup$

I have a grammar,

$L \to A \langle A \rangle^*$

$A \to () \mid (L)$

but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^*T\rangle^*$ then I can create parser like

proc E begin 
  T; 
  while symbol='*' do 
    T 
  od 

However in my case don't have any symbol. So how can I check symbol for while process? Or my grammar is incorrect?

$\endgroup$
  • 1
    $\begingroup$ I tried to make sense of your LaTeX; which stars are Kleene, which are symbols? $\endgroup$ – Raphael Feb 11 '15 at 8:32
0
$\begingroup$

From the first rules, it seems clear that the angle brackets are metasyntactic parenthesis used to denote Kleene closure over more than a single symbol. This is also suggested by the existence of normal brackets in the grammar. This also suggest that the example rule for $E$ is syntactically not well formed and means nothing at all, since the star cannot apply to a metasyntactic parenthesis (as the first star seems to be doing). The correct rule is probably: $E \to T \langle +T\rangle^*$ and the corresponding parser:

proc E begin 
  T; 
  while symbol='+' do 
    T 
  od 

Generating a parser for $\langle A \rangle$ is just generating a parser for $A$ alone. The angle brackets are just grammatical notation (like the arrow or the vertical bar), and are not supposed to appear in generated strings.

They are not necessary here, but could be if you had Kleene star over several symbols, such as $\langle AB \rangle^*$, as in my corrected version of the rule for $E$.

With these corrections, you should be able to finish your recursive descent parser.

$\endgroup$
0
$\begingroup$

You do have a symbol, "$($". A bit more generally though (if I understand the notation you're using), if you're processing an $L$ and you see anything, it must come from an $A$, if it's not an error, so you can recurse to processing an $A$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.