1
\$\begingroup\$

In the process of creating my first toy language, I have created the base grammar for it (which can surely be improved upon, feel free to comment). I am emitting C at the moment.

\begin{align} program &\rightarrow (declaration | stmt)^* \\ declaration &\rightarrow \textbf{let}\ assignment\ |\ \textbf{let}\ identifier \\ stmt &\rightarrow assignment\ |\ returnStmt\ |\ printStmt \\ assignment &\rightarrow identifier = expr\\ returnStmt &\rightarrow \textbf{return}\ \epsilon\ |\ \textbf{return}\ expr\\ printStmt &\rightarrow \textbf{print}\ \text{STRCONST} \\ expr &\rightarrow mathExpr\ |\ comparison \\ comparison &\rightarrow term\ compOp\ term \\ mathExpr &\rightarrow term\ (addOp\ term)^*\\ term &\rightarrow factor\ (mulOp\ factor)^*\\ factor &\rightarrow identifier\ |\ \text{INTCONST} \\ addOp &\rightarrow (+ | -) \\ mulOp &\rightarrow (* | /) \\ compOp &\rightarrow (<|>|<=|>=|==|!=) \\ \end{align}

I am reading from a few sources, trying to wrap my head around how the grammar should be constructed and how to parser should reflect every production the grammar can create. The general idea seems to be (and sounds to me like the most logical course of action), that the parser's functions should follow the grammar, i.e. each non-terminal has it's own function, productions separated by | are made into if statements, productions with Kleene star (*) are made into loops etc.

While implementing the expressions (expr) in code however, I have found the most reasonable way to code this requires recursion, therefore deviates from this principle. Whereas until expr, I had classes that exactly reflected the grammar for each non-terminal, for example stmt is represented by:

internal class Assignment : Statement {
    public Identifier ident { get; set; }
    public Expression expr { get; set; }
}

internal class ReturnStatement : Statement {
    public Expression expr { get; set; }
}

internal class PrintStatement : Statement {
    public StrConst strConst { get; set; }
}

For comparison, mathExpr and term I have created the BinaryExpression class which seems the most logical thing to do:

internal class BinaryExpression : Expression {
    public Expression left { get; set; }
    public Expression right { get; set; }
    public string op {get; set;}
}

The parsing code is therefore not reflecting of the grammar. What worries me is that, even though this works, it could be hard to extend if I ever need to complicate the grammar further. My main question: I am not sure if the recursive code shows that the grammar could be rewritten in a different way to reflect it, if the code could be rewritten to reflect the existing grammar without too much spaghetti, or if this is just fine as it is.

Parsing code for the expressions below (please tell me if I should post more code for context):

Expression parseExpression() {
    int storePos = pos;
    BinaryExpression comparison = parseComparison();
    if (comparison != null) {
        return comparison;
    }
    // Restore position of token being read since comparison failed.
    pos = storePos;
    Expression mathExpr = parseMathExpression();
    if (mathExpr != null) {
        return mathExpr;
    }
    else {
        logError("expression");
    }

    return null;
}

BinaryExpression parseComparison() {
    Expression left = parseTerm();
    if (left != null) {
        if (match(comparisonOperators)) {
            string op = currentToken().lexeme;
            consume();
            Expression right = parseTerm();
            if (right != null) {
                return new BinaryExpression() { left = left, right = right, op = op };
            }
            else {
                logError("term");
                return null;
            }
        }
        else {
            // could be math expression, so do not log any error here
            return null;
        }
    }
    else {
        logError("term");
    }
    return null;
}


Expression parseMathExpression() {
    Expression left = parseTerm();
    if (left != null) {
        if (match(addOperators)) {
            BinaryExpression expr = new BinaryExpression() { left = left, op = currentToken().lexeme };
            consume(); // operator
            expr.right = parseMathExpression();
            return expr;
        }
    }
    else {
        logError("term");
    }
    return left;
}

Expression parseTerm() {
    Expression left = parseFactor();
    if (left != null) {
        if (match(factorOperators)) {
            BinaryExpression expr = new BinaryExpression() { left = left, op = currentToken().lexeme };
            consume(); //operator
            expr.right = parseTerm();
            return expr;
        }
    }
    else {
        logError("factor");
    }
    return left;
}

Expression parseFactor() {
    if (match(TokenType.IntegralLiteral)) {
        if (int.TryParse(currentToken().lexeme, out int result)) {
            consume();
            return new Factor() { intConst = new IntConst() { value = result } };
        }
        else {
            logError("integer");
        }
    }
    else if (match(TokenType.Identifier)) {
        var fac = new Factor() { ident = new Identifier() { name = currentToken().lexeme } };
        consume();
        return fac;
    }
    else {
        logError("identifier or literal");
    }
    return null;
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Bearing in mind that the c# tag was removed in revision 2 based on prior comments, what language is the compiler written in? I see int.TryParse() is utilized which appears to be provided by the .net Framework so perhaps it is c# or a similar language \$\endgroup\$ Mar 18 at 15:24
  • 1
    \$\begingroup\$ Please include a tag for the language you wrote this in. Language tags are not optional. \$\endgroup\$
    – Mast
    Mar 18 at 16:34
  • \$\begingroup\$ It is indeed c#. I initially had the tag but someone asked why it was there and it made sense to me that this question could be language agnostic. \$\endgroup\$
    – Tsaras
    Mar 19 at 13:37

2 Answers 2

4
\$\begingroup\$

The first answer already contains a few points that I do not want to repeat.

Your grammar is not recursive, but it should be. Why? Because without it you quickly end up in a dead end. E.g., you can express a*b + c, but not (a+b) * c because factors cannot contain mathExpr.

A recursive grammar requires recursive calls in the parser. This reflects the principle "the parser should reflect every production of the grammar" and does not deviate from it.

Also, you split expr into mathExpr and comparison; however, those should be in a hierarchy reflecting the operator precedence instead of existing in parallel. Exactly like mathExpr is not term | factor.

Whether an expression is of type Integer or Boolean should not be a matter of the grammar but of semantics. E.g., is a == s allowed? If a and b are of the same type then yes, but if a is int and s is string, then probably not. Many programmers think that if-statements require a comparison and therefore, we often see statements like If b = True Then. No, they do not. They require an expression of Boolean type or an expression implicitly convertible to Boolean. This can also be a variable or a method call as in If b Then or If IsValid(x) Then.

expr -> simpleExpr (compOp simpleExpr)?

simpleExpr -> term (addOp term)*

term -> factor (mulOp factor)*

factor -> IDENTIFIER | LITERAL | "(" expr ")"

In factor I changed two things (besides making identifier a terminal symbol):

  1. I replaced INTCONST with LITERAL. A constant can also designate an identifier declared as const int N = 10; whereas a literal is something like 7, true or "hello". You are missing Boolean literals. E.g., you cannot express let b = true. Now, a literal could be an integer or Boolean literal.
  2. I added the term "(" expr ")". This is where recursion comes into play. This makes the grammar immensely powerful as it allows expressions of arbitrary complexity to be written.
\$\endgroup\$
3
\$\begingroup\$

You are writing a recursive descent parser. Not unreasonable for something simple.

The * is handled like this:

Expression parseTerm() {
    Expression left = parseFactor();
    if (left != null) {
        while (match(factorOperators)) {
            BinaryExpression expr = new BinaryExpression() { left = left, op = currentToken().lexeme };
            consume(); //operator
            expr.right = parseFactor();
            left = expr;
        }
    }
    else {
        logError("factor");
    }
    return left;
}

There are a few other issues:

  1. IDENTIFIER is a terminal
  2. you haven't allowed for let a = x > y + 1. This could be deliberate or an oversight.
  3. Your error handling is excessive. parseTerm() does not need to re-report the error it received from parseFactor.
  4. And your error handling may be insufficient. You should consider what error handling to do in the second call to parseFactor. (You could, for instance, return expr immediately.) You might also consider having a ParseError object that can be returned instead of null (which would mean you don't need to do anything in the previous case).
  5. You will get recursion when you introduce parentheses, but that will match the grammar.

P.S. Plan for lots and lots of tests. Consider these:

let = 3
let a = 3
let a b = 3
let a b c = 3

Two of these lines are valid in your grammar.

\$\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.