时间戳

首页 > 解决方案 > 如何在 LL(1) 解析器中处理运算符优先级

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

问题描述

我正在为表达式语法编写一个 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，解析器如何知道在加法之前评估乘法？

标签： parsingcompiler-constructiongrammarll

解决方案

尝试这个：

; 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

推荐阅读