🦸 [Need Help] Operator-precedence parser 🦸

[BaseMax]

Hi, I took the initial phase of the parser forward and it works well and detects tokens.

Now I need help arranging operations and operators. Does anyone want to help? (Operator-precedence parser)
for e.g:

expression ::= equality-expression
equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) *
additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) *
multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary

here is cpp's operator precedence https://en.cppreference.com/w/cpp/language/operator_precedence im pretty sure its common sense using bidmas i can help if need be.

[BaseMax]

LexAndYacc.pdf
OperatorPrecedenceParsing.pdf

[BaseMax]

Thank you for your message.

Okay, honestly I not sure about some special operators. such as >> << and etc.
I aware Operator-precedence is different in every language. So I not sure how we can go up.
I think we can figure out how PHP works by thinking about its Operator-precedence parser.

• https://github.com/php/php-src/blob/master/Zend/zend_language_scanner.l
• https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y

[BaseMax]

I checked its parser. They did not divide the phrase into several groups.
And he manages these using BISON. https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y#L1041
Since we are writing Parser by hand, we need to group and know more details.

• https://www.tutorialspoint.com/cprogramming/c_operators_precedence.htm
• https://en.cppreference.com/w/c/language/operator_precedence

[BaseMax]

Dear @snapogod;
#71 (comment)

Can you help us complete the BNF grammar? https://github.com/One-Language/One/blob/master/grammar.BNF
We need to know grammar of all operators.

[BaseMax]

Another nice implementation of the expression parser. But it does not help us much.
https://github.com/maxicombina/c-calculator/blob/master/calculator.c#L170

int get_op_precedence(char op)
{
    int res = 0;
    if (op == '+' || op == '-')
    {
        res = 9;
    }
    else if (op == '*' || op == '/' || op == '%')
    {
        res = 10;
    }
    else if (op == '^')
    {
        res = 11;
    }
    return res;
}

static int is_higher_or_equal_precedence(char op1, char op2)
{
    return get_op_precedence(op1) >= get_op_precedence(op2);
}

static int is_higher_precedence(char op1, char op2)
{
    return get_op_precedence(op1) > get_op_precedence(op2);
}

static int is_left_assoc_operator(char op)
{
    return (op == '+' || op == '-' || op == '*' || op == '/' || op == '%');
}

static int is_right_assoc_operator(char op)
{
    return (op == '^');
}

[BaseMax]

Some useful references I find yesterday:
https://depositonce.tu-berlin.de/bitstream/11303/2630/1/Dokument_46.pdf
https://cdn2.hubspot.net/hubfs/3881487/ExprParser_User_Guide.pdf?t=1517563829446

[BaseMax]

Another nice implementation of the expression parser:
https://github.com/programoworm/Expression_Recogniser/blob/master/expression.c

This is something I extracted from the above code but it is still incomplete and has a problem:

parseFactor = "+" parseFactor # need Fix
                    = "-" parseFactor # need Fix
                    = "(" INT ")"
                    = INT

parseTerm = parseFactor
                  = parseFactor "*" parseFactor
                  = parseFactor "/" parseFactor

parseExpressions = parseTerm
                              = parseTerm "+" parseTerm
                              = parseTerm "-" parseTerm

[BaseMax]

I found some online tools that can test grammar.
This is very interesting and it is better to test the grammars in the same way.

• https://mdkrajnak.github.io/ebnftest/
• https://bnfplayground.pauliankline.com/

More about this subject:

• http://www.nongnu.org/bnf/
• https://github.com/codelion/gramtest
• https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

But I'm looking for something that can draw a picture and show it with a figure ... Do you know anything?

[BaseMax]

Another nice example from PEG.JS:

// Simple Arithmetics Grammar
// ==========================
//
// Accepts expressions like "2 * (3 + 4)" and computes their value.

Expression
  = head:Term tail:(_ ("+" / "-") _ Term)* {
      return tail.reduce(function(result, element) {
        if (element[1] === "+") { return result + element[3]; }
        if (element[1] === "-") { return result - element[3]; }
      }, head);
    }

Term
  = head:Factor tail:(_ ("*" / "/") _ Factor)* {
      return tail.reduce(function(result, element) {
        if (element[1] === "*") { return result * element[3]; }
        if (element[1] === "/") { return result / element[3]; }
      }, head);
    }

Factor
  = "(" _ expr:Expression _ ")" { return expr; }
  / Integer

Integer "integer"
  = _ [0-9]+ { return parseInt(text(), 10); }

_ "whitespace"
  = [ \t\n\r]*

https://pegjs.org/online

[BaseMax]

The above codes are summarized as follows:

Expression   = Term ( ("+" / "-")  Term)*
                         | Term

Term  = Factor ( ("*" / "/") Factor)*

Factor   = "(" Expression ")"
               | [0-9]+

The problem is that this grammar is not complete and does not include dozens of operators!