标签: parser-generator

我正在尝试实现LALR解析器生成器,如"编译器原理技术和工具"(也称为"龙书")中所述.

很多已经有效.解析器生成器当前能够生成完整的转到图.

Example Grammar:
                   S' --> S
                   S  --> C C
                   C  --> c C
                   C  --> d

Nonterminals: S', S, C
Terminals: c, d
Start: S'

转到图:

I[0]---------------+      I[1]-------------+
| S' --> . S   , $ |--S-->| S' --> S . , $ |
| S  --> . C C , $ |      +----------------+
| C  --> . c C , c |
| C  --> . c C , d |      I[2]--------------+
| C  --> . d   , …

什么是FIRST和FOLLOW集？它们在解析时使用了什么？它们用于自上而下或自下而上的解析器吗？

任何人都可以解释我FIRST和FOLLOW SETS为以下语法规则集:

> E := E+T | T
> 
> T := T*V | T
> 
> V := <id>

我听说"真正的编译器编写者"使用自己的手工解析器而不是使用解析器生成器.我也听说过解析器生成器不会为真实语言剪切它.据说,使用解析器生成器很难实现许多特殊情况.我对此表示怀疑:

1. 从理论上讲,GLR解析器生成器应该能够处理大多数编程语言设计(除了C++ ......)
2. 我知道至少有一种使用解析器生成器的生产语言:Ruby [1].
3. 当我在学校学习编译器课程时,我们使用了解析器生成器.

所以我的问题是:使用解析器生成器编写生成编译器,或使用解析器生成器被编译器社区认为是一个糟糕的设计决策是否合理？

[1] https://github.com/ruby/ruby/blob/trunk/parse.y

我正在使用Happy构建解析器,并注意到这是在线文档:

和yacc一样,我们在这里包含%%,没有任何正当理由.

%%

必须有一个理由,即使它是微不足道的.有谁知道它是什么？

我必须将很多文件从Mathematica移植到Octave.我在1991年找到了一个Lisp Mathematica解析器,但我并不熟悉Lisp,所以我想知道是否有人有任何移植方向的经验.在研究并向WolframAlpha发送电子邮件并且没有实际结果之后,我将不得不使用Lex和Yacc来生成交叉编译器.这对我来说似乎有些过分.

任何提示或指示将不胜感激.

澄清:

我开始使用很多Mathematica文件,他们的功能必须移植到Octave.我只是希望在尽可能短的时间内实现这一目标,因为这是我老板在节假日期间给我做的一项任务.感谢您的帮助,我将查看FullForm并检查Mathematica文件中的非便携式内容.如果只能转换一定数量的文件,我将不得不手工完成其余的工作,这需要一些时间.所以这基本上是从一个程序转移到另一个程序的一次性事情.

正如列昂尼德的帖子所述,任务似乎过多,但我是学生研究助理,这正是我必须在我的部门完成的任务.

我在创建一个简单的语法时遇到了麻烦,我支持函数调用.
我正在使用Greg的基于柠檬的PHP_ParserGenerator.

这是语法的相关部分:

program ::= expr(A).                        { $this->result = A; }

value(A) ::= SIMPLE_STRING(B).              { A = B; }
value(A) ::= NUMBER(B).                     { A = B; }
value(A) ::= CONTEXT_REFERENCE(B).          { A = B; }

arg_list ::= arg_list SEPARATOR value(B).   { $this->args[] = B; }
arg_list ::= value(B).                      { $this->args[] = B; }
arg_list ::= . 

expr(A) ::= SIMPLE_STRING(B) PAREN_LEFT arg_list PAREN_RIGHT. { A = call_user_func_array(B, $this->args); }

expr(A) ::= CONTEXT_REFERENCE(B). {
    list($context, $key) = explode('.', B);
    A = $this->context[$context][$key]; …

我这里有一个JISON计算器示例的略微修改版本:

/* description: Parses end executes mathematical expressions. */

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?\b  return 'NUMBER'
"*"                   return '*'
"/"                   return '/'
"-"                   return '-'
"+"                   return '+'
"^"                   return '^'
"!"                   return '!'
"%"                   return '%'
"("                   return '('
")"                   return ')'
"PI"                  return 'PI'
"E"                   return 'E'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

/* operator associations and precedence */

%left '+' '-'
%left '*' '/'
%left '^'
%right '!'
%right …

我使用yapps为金字塔内的LaTex-ish语言生成解析器(例如将类似\begin{itemize}的东西翻译成相应的<ul>-Tags).一个命令(即\ref{SOMEID})应该通过route_url(或route_path)的调用构造一个路由并将id传递给它.由于此调用发生在由yapps生成的代码和我定义的语法的深处,我认为没有任何可能将请求对象传递给它.

是否存在某种全局请求对象？或者,因为我预见到我不应该使用它,是否有可能在没有请求对象的情况下构造路由(取决于参数)？

我正在编写一个LALR解析器生成器作为一个宠物项目。

我正在使用紫色的龙书来帮助我进行设计，并且从中收集的信息是解析器中有四种错误恢复方法：

• 紧急模式：开始转储输入符号，直到找到由编译器设计人员预先选择的符号
• 词组级恢复：将输入字符串修改为可以减少当前产量的内容
• 错误产生：通过将错误合并到语法中来预测错误
• 全局更正：短语级别恢复的版本更加复杂（据我所知）

其中两个需要修改输入字符串（我想避免），另外两个需要编译器设计人员预见错误并根据他们对语言的了解来设计错误恢复。但是解析器生成器也具有关于语言的知识，因此我很好奇是否有更好的方法可以从解析错误中恢复而无需预先选择同步标记或用错误产生物填充语法。

解析器不能只选择同步令牌，而不能仅选择当前生产可以减少为同步令牌的所有非终结符后面的符号？我还没有真正弄清楚它的效果如何-我将解析器形象化地放在了一系列正在进行中的产品中，但是，这当然不是自底向上解析器的工作方式。试图找到可行状态会产生太多无关的错误吗？它会尝试以无效状态恢复解析器吗？有没有一种很好的方法来用有效的错误操作预填充解析器表，以便实际的解析程序不必在遇到错误时就知道下一步应该去哪里？

如何在erlang中创建一个解析器,它将采用一个正确形成的命题公式并将其转换为一些内部表示.

列出在erlang中创建解析器的可用工具以及使用它们的项目可能会有所帮助.