0
$\begingroup$

Suppose we have the grammar

$$S \to aA | BA $$ $$A \to a | bB | \epsilon $$ $$ B \to cB | d$$

I know that I need to write four different functions in order to parse this grammar.

They are

parse_input(),

parse_S(),

parse_A(), and

parse_B()

However, I am having trouble coming up with a parser for this short grammar. Does this look right?

parse_input():
    if (peek(1) = a AND peek(2) = A)
        parse_S()
    else if (peek(1) = a OR peek(1) = B)
        parse_A()
    else if (peek(1) = c or peek(1) = D)
        parse_B()

parse_S()
    if (peek(1) = a)
        expect(a)
        parse_A()
    else
        parse_B()

parse_A():
    if (peek(1) = a)
        expect(a)
    else if (peek(1) = b)
        expect(b)
        parse_B()
    else if (peek(1) = $\epsilon$)
       expect($\epsilon$)

parse_B():
    if (peek(1) = c)
        expect(c)
        parse_B()
    else if (peek(1) = d)
        expect(d)
    else 
        syntax_error()

but after that, I am stuck.

$\endgroup$
2
  • $\begingroup$ Are you trying to write a recursive descent parser? $\endgroup$ Feb 18, 2022 at 5:44
  • $\begingroup$ @PawanNirpal yes, but just basic pseudocode to help me understand parsing. it doesn't need to be fully functional and capture all possible errors. just one to validate the grammar $\endgroup$
    – zzzz
    Feb 18, 2022 at 5:53

1 Answer 1

1
$\begingroup$

$peek(i)$ (presumably) returns the $i^{th}$ next token from the input stream. $A$ is not a token; it's a non-terminal, aka grammar variable, which denotes the result of a recursive parse of a substring of the input. So $peek(2)$ cannot return $A$.

But in some sense that doesn't matter, because the goal is to parse without ever peeking beyond the next token, and that's certainly possible for this grammar. Once you know that the next token is $a$, you know to predict $S\to aA$, and you know what you must do: match the $a$ and then parse the $A$. Of course, it's possible that parsing $A$ will fail, but that error will be noted in the course of the parse.

Equally, $peek(1)$ cannot return $B$, so you are asking the wrong question in that line. What you want to know is whether the next token could be the first token of a substring derived from $B$; in other words $peek(1)\in FIRST(B)$, where $FIRST(B)$ is the set of tokens which could be at the start of a derivation of $B$. Given a grammar, it's easy to compute the $FIRST$ set for each non-terminal.

Since $a$ is not in $FIRST(B)$, it's not totally necessary to test whether $peek(1)\in FIRST (B)$. You could just call $parseB()$, which will fail if the first token is wrong. Using default actions can simplify parsers but it can also lead to unexpected side effects before errors are discovered, if the parse actions have side effects. So your implementation of $parseS()$ is fine.

But your implementation of $parseA$ attempts to check whether $peek(1)$ is $ε$, which is non-sensical. $ε$ is not a token. It's an empty sequence of tokens. In other words, it's nothing. If you were to ask "can $A$ start with nothing?", the answer would be immediately be "yes, of course". You don't need to know anything about $A$ other than that it derives at least one possible string, because the empty sequence is a proper prefix of every possible sequence, even the empty sequence itself. So if you get to that point in the control flow, you can just return; the parse of $A$ succeeded by successfully matching nothing.

I could go on, but I think you would find it more valuable to read a chapter in some introductory parsing text about top-down parsing, and make sure you understand the basic concepts: terminals and non-terminals, derivations, FIRST and FOLLOW sets. None of it is complicated.

$\endgroup$

Your Answer

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

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