从类 BNF 语法到 Java 或 C++
From BNF-like grammar to Java or C++
我会将此代码用于非常基本的计算器编译器和解释器。
如何将此语法转换为 C++ 或 Java?
expr ->term moreterms
moreterms -> +term {print(‘+’)} moreterms
|‐term {print(‘‐’)} moreterms
|ε
term ->factor morefactors
morefactors ->*factor {print(‘*’)} morefactors
|/factor {print(‘/’)} morefactors
|ε
factor ->(expr)
|id {print(id)}
|num {print(num)}
你看过Yacc了吗?这可能正是您正在寻找的。
从 Yacc 到提振精神,有许多工具可以提取语法并生成解析器。
编写解析器的艺术已被广泛研究。这不是微不足道的。一种方法是确定您是否可以将 BNF 转换为 LR(1) 文法并为其编写 LR 解析器。
一种简单的解析方法是将解析分为标记化(将事物捆绑到标识符中)和语法树生成。
Wikipedia has a cursory description of LR parsing. Knuth's Canonical LR(1) parser也值得一看
教授如何编写 LR(1) 解析器(有任何限制,更不用说 LR(k) 解析器)是短期大学课程或书籍章节的问题,而不是堆栈溢出 post.
但总体思路是您从左到右阅读。您向前看 k 个标记(通常为 1 个)以确定将哪个规则应用于您遇到的下一个标记。您自下而上构建解析树。
有很多技术细节、技巧、怪癖和问题。不是每个 BNF 文法都可以变成 LR(1) 文法,更不用说许多解析生成器可以处理的受限文法了。