How to parse this grammar?

Question

I want to create a recursive descendant parser in java for following grammar (I have managed to create tokens). This is the relevant part of the grammar:

expression ::= numeric_expression | identifier | "null" 
identifier ::= "a..z,$,_"
numeric_expression ::= ( ( "-" | "++" | "--" ) expression )
      | ( expression ( "++" | "--" ) )
      | ( expression ( "+" | "+=" | "-" | "-=" | "*" | "*=" | "/" | "/=" | "%" | "%=" ) expression )
arglist ::= expression { "," expression }

I have written code for parsing numeric_expression (assuming if invalid token, return null):

    NumericAST<? extends OpAST> parseNumericExpr() {
        OpAST op;
        if (token.getCodes() == Lexer.CODES.UNARY_OP) { //Check for unary operator like "++" or "--" etc
            op = new UnaryOpAST(token.getValue());

            token = getNextToken();
            AST expr = parseExpr();        // Method that returns expression node.
            if (expr == null) {
                op = null;
                return null;
            } else {
                if (checkSemi()) {
                    System.out.println("UNARY AST CREATED");
                    return new NumericAST<OpAST>(expr, op, false);
                }
                else {
                    return null;
                }
            }
        } else {   // Binary operation like "a+b", where a,b ->expression
            AST expr = parseExpr(); 
            if (expr == null) {
                return null;
            } else {
                token = getNextToken();
                if (token.getCodes() == Lexer.CODES.UNARY_OP) {
                    op = new UnaryOpAST(token.getValue());
                    return new NumericAST<OpAST>(expr, op, true);
                } else if (token.getCodes() == Lexer.CODES.BIN_OP) {
                    op = new BinaryOpAST(token.getValue());
                    token = getNextToken();

                    AST expr2 = parseExpr();
                    if (expr2 == null) {
                        op = null;
                        expr = null;
                        return null;
                    } else {
                        if (checkSemi()) {
                            System.out.println("BINARY AST CREATED");
                            return new NumericAST<OpAST>(expr, op, expr2);
                        }
                        else {
                            return null;
                        }

                    }
                } else {
                    expr = null;
                    return null;
                }
            }
        }
    }

Now, if i get a unary operator like ++ i can directly call this method, but I dont know to recognize other grammar, starting with same productions, like arglist and numeric_expression having "expression" as start production.

My question is:

How to recognize whether to call parseNumericExpr() or parseArgList() (method not mentioned above) if i get an expression token?

Hi, just to clarify, is that your full grammar definition? You seem to be using UnaryOperatorAST in your code, but unary operator expression does not seem to be a building block in your grammar. — Paul Benn
This question is to broad, actually it is many questions in one. Please focus your question one one specific issue and remember this is not a code review site. — Joakim Danielson

rici rici · Accepted Answer · 2019-12-10T00:51:22

In order to write a recursive descent parser, you need an appropriate top-down grammar, normally an LL(1) grammar, although it's common to write the grammar using EBNF operators, as shown in the example grammar on Wikipedia's page on recursive descent grammars.

Unfortunately, your grammar is not LL(1), and the question you raise is a consequence of that fact. An LL(1) grammar has the property that the parser can always determine which production to use by examining only the next input token, which puts some severe constraints on the grammar, including:

No two productions for the same non-terminal can start with the same symbol.
No production can be left-recursive (i.e. the first symbol on the right-hand side is the defining non-terminal).

Here's a small rearrangement of your grammar which will work:

-- I added number here in order to be explicit.
atom       ::= identifier | number | "null" | "(" expression ")"
-- I added function calls here, but it's arguable that this syntax accepts
-- a lot of invalid expressions
primary    ::= atom { "++" | "--" | "(" [ arglist ] ")" }
factor     ::= [ "-" | "++" | "--" ] primary
term       ::= factor { ( "*" | "/" | "%" ) factor }
value      ::= term { ( "+" | "-" ) term }
-- This adds the ordinary "=" assignment to the list in case it was
-- omitted by accident. Also, see the note below.
expression ::= { value ( "=" | "+#" | "-=" | "*=" | "/=" | "%=" ) } value
arglist    ::= expression { "," expression }

The last expression rule is an attempt to capture the usual syntax of assignment operators (which associate to the right, not to the left), but it suffers from a classic problem address by this highly related question. I don't think I have a better answer to this issue than the one I wrote three years ago, so I hope it is still useful.

How to parse this grammar?

1 Answers