如何处理 LL(1) 解析器中的运算符优先级

Question

我正在为表达式语法编写 LL(1) 解析器。我有以下语法：

E -> E + E
E -> E - E
E -> E * E
E -> E / E
E -> INT

然而，这是左递归的，我用以下语法删除了左递归：

E -> INT E'
E' -> + INT E'
E' -> - INT E'
E' -> * INT E'
E' -> / INT E'
E' -> ε

如果我要使用表达式 1 + 2 * 3，解析器如何知道在加法之前计算乘法？

Answer 1

试试这个：

; an expression is an addition
E   -> ADD          

; an addition is a multiplication that is optionally followed
; by +- and another addition
ADD -> MUL T  
T   -> PM ADD
T   -> ε
PM  -> +
PM  -> -

; a multiplication is an integer that is optionally followed
; by */ and another multiplication
MUL -> INT G
G   -> MD MUL
G   -> ε
MD  -> *
MD  -> /

; an integer is a digit that is optionally followed by an integer
INT -> DIGIT J
J   -> INT
J   -> ε

; digits
DIGIT -> 0
DIGIT -> 1
DIGIT -> 2
DIGIT -> 3
DIGIT -> 4
DIGIT -> 5
DIGIT -> 6
DIGIT -> 7
DIGIT -> 8
DIGIT -> 9

如何处理 LL(1) 解析器中的运算符优先级

How to handle operator precedence in an LL(1) parser

compiler-construction

grammar

parsing

ll