5

首先，我正在用 Python 制作解释器，而不是编译为机器代码的实际编译器。我最近浏览了很多编译器构建指南，我了解为解析器生成标记和构建语法树以评估算术表达式的基础知识，但我不太了解如何解析带有函数调用的表达式，像

图（一）

1 + pow(1, 1)

或者当用户定义这样的函数时如何解析行

图（b）

function newFunction( someArgs ){
   ... some magic ...
}

在图（a）中，我应该如何标记这个表达式？在阅读了保留字“pow”之后，我是否应该将所有内容都抓取到右括号并将其传递给解析器？或者我应该将“pow”、“(”、“1”、“1”和“)”分别作为单独的标记添加到我的解析树中吗？

在斐波那契。(b) 在编译函数定义时，我什至不知道从哪里开始。任何让我朝着正确方向前进的信息将不胜感激。

编辑：我正在使用 Backus-Naur 形式语法：

S ::= 表达式

表达式 ::= 术语 | 术语（[+-] 术语）+

术语 ::= 因子 | 因子（[*/] 因子）+

因子 ::= 数字 | （ 表达 ）

数字 ::= [0-9]+

4

2 回答 2

3

另一张海报建议将函数名称添加到您的语法中。

这适用于玩具语言，但不适用于可能有大量库和大量用户定义函数的实际语言。

您可以通过将函数调用添加到 BNF 来处理后者，以将函数名称排除在语法之外：

S ::= expression

expression ::= term | term ([+-] term)+

term ::= factor | factor ([*/] factor)+

factor ::= number | ( expression ) | identifier |  functioncall

functioncall ::= identifier [(]  arguments [)]

arguments ::= empty | arguments 

arguments ::= expression |  arguments [,] expression

number ::= [0-9]+

identifier ::= [a-z]+

现在您的解析器可以接收函数调用。（语法中没有定义函数的方法......但这只是更多的语法，我留给你添加）。

这样做的代价是，在解析之后，某些东西已经决定了每个函数名，确切地说它代表了哪位代码。您将需要一个符号表来执行此操作。那是另一个问题。

于 2015-01-11T16:53:15.300 回答
1

希望这个问题会有一些好的答案，但我建议您做的第一件事是帮助提高问题的质量：

  1. 限制您的语言范围和
  2. 定义你的语法。

查看Backus-Naur Form并了解如何定义您的语言将支持的语法。

首先，考虑为少数数学函数编写一个简单的解析器，以了解它。

<digit>   ::= "0"|"1"|...|"9"
<integer> ::= <digit>*
<expr>    ::= <integer> | <add> | <pow>
<add>     ::= "add(" <expr> "," <expr> ")"
<sub>     ::= "sub(" <expr> "," <expr> ")"
<pow>     ::= "pow(" <expr> "," <expr> ")"

从这样的正式语法中，您可以确定什么是或不是有效的表达式。

例如：add(1,2)and在 as is not 的pow(2,add(2,1))情况下都是有效的，因为语法需要两个表达式。add(1)add

于 2013-09-16T05:29:28.330 回答