非终结符号和符号规则解释，特别是 expr 保留？

Question

 %{
 #include <stdio.h>
 #include <stdlib.h>
 void yyerror(const char*);
 %}
 %token WORD
 %token EOL
 %%
 input:
 /* empty */
 |
 input line
 ;
 line:
 EOL { exit(1); }
 | words EOL { printf("correct!\n"); }
 ;
 words:
 words WORD
 | WORD
 ;
 %%
 void yyerror(const char *str)
 {
 fprintf(stderr," error: %s\n",str);
 }
 main()
 {
 yyparse();
 }

谁能帮我理解非终端符号和符号规则，比如行输入词 expr 。expr 是保留字吗？？

Answer 1

看起来您完全是一个使用像 bison 这样的解析器生成工具的新手。虽然您有一个小的工作示例程序，但您想要扩展它，但不完全理解它是如何工作的，或者不理解您正在使用的文档中使用的一些术语。我将在以代码结尾的教程中解释这些要点，该代码使用表达式扩展您的示例。

为了使本教程更具可读性，一些解释在您将鼠标悬停之前会隐藏起来。这使任何人都可以只阅读他们需要的部分，并使页面不再像一堵文字墙。

野牛概览

Bison Manual is a good source of reference for questions on using bison. The first thing to note is the overall layout of bison code是这样的：

%{

序言

%}

野牛声明

%%

语法规则

%%

结语

第一部分是Prologue，用于放置生成代码的声明和导入（通常在C.

第二节是bison declarations，介绍语法中使用的终结符号，并可选地指明start语法规则。

第三部分包含匹配规则时要采用的（无上下文）grammar rules and actions。这些规则被bison工具转换成输出语言（通常是C）的解析器。这通常是任何野牛文件的主体。

第四个也是最后一个部分包含 epilogue。这用于放置应复制到输出文件中的任何代码。它通常包含前面使用的规则操作中所需函数的任何代码。

语法规则

了解野牛使用的语法规则涉及一些计算机科学研究。它通常是没有学过计算机科学的程序员遇到麻烦的领域之一，因此有时需要进一步解释。语法规则用于定义哪些符号序列在语言中有效。解析是将输入与这些规则匹配的过程。 Bison 的工作是构建一个实现这些规则的解析器。这些规则指定了称为 tokens 的输入实体序列，这些实体在 bison 声明部分中定义。标记和其他输入符号在语法中称为 terminal 符号。规则被赋予名称，规则的名称称为语法的非终结符。规则的形式为：

rule: sequence of TERMINALS and non terminals ;

根据约定终端名称大写，非终端名称不大写。

一个例子：

declaration : ID ":" ID ;

此规则定义非终结符声明以匹配令牌序列 ID，“：”，ID 的顺序。请注意，我们可以在该规则中包含字符串和标记名称。

这些规则可以添加 actions，定义规则匹配发生时要执行的代码。操作放在每个规则末尾的 { ... } 对中，如下所示：

declaration : ID ":" ID { printf("Matched a declaration\n"); }
            ;

对于高级用法，我们还可以从令牌中提取信息以包含在我们的操作中：

declaration : ID ":" ID { printf("%s declared of type %s\n",getSymbol(),getSymbol()); }
            ;

现在我们已经介绍了什么是终端和非终端符号的基础知识，让我们用它来解码示例程序你用过...

带注释的示例

%{

中的%{是pair的开头`%{ ... }%是要复制的标记代码进入 bison 生成的 C 代码的序言。它允许声明和要插入的导入。

 #include <stdio.h>
 #include <stdlib.h>
 void yyerror(const char*);

我们导入标准 C 库以便我们可以进行打印。我们声明我们使用 yyerror
%} 结束序言

 %}
 %token WORD
 %token EOL
 %%

这是 bison 声明部分，表示我们从词法分析器导入名为 WORD 和 EOL 的标记。词法分析器代码在别处定义，所以我们不知道这些标记代表什么字符序列。不过我们可以从他们的名字中猜出！
%% 标记声明的结束和规则部分的开始在 %% 之后遇到的第一个规则被认为是语法的开始，除非在声明部分使用 %start 指令来命名另一个开始。

 input:
 /* empty */

这定义了一个名为 input.
的规则（或非终结符）该规则仅包含一条注释，这实际上意味着一个空字符串或一个空文件是名为 input 的规则的有效匹配项。这意味着允许解析器解析任何内容！如果遗漏了这一点，就无法指定一行是什么。正如在下面的规则中，行总是根据没有出路的行来定义的。

 |
 input line

大棒符号 | 表示或或称为 input 的非终端的替代规则。替代规则是 input line。这与写作相同：
input : input line

分号 ; 标记行的语法规则（非终结符）结束。上下文无关文法的知识将告诉我们这个规则匹配任意长度的可选行序列。定义一行的内容由后面的非终结符 'line' 定义。

 line:
 EOL { exit(1); }
 | words EOL { printf("correct!\n"); }
 ;

这将非终端行定义为无限行序列，每行可选地包含 words 并由 token/terminal EOL 终止。当一行匹配时，字符串 correct 被打印出来。不包含单词（空）的行将结束解析，解析器将退出。

 words:
 words WORD
 | WORD
 ;

这里定义了非终结符叫词，它是token/terminal叫WORD的无限序列。

%%

这标志着 bison 规则部分的结束。在此之后的所有代码都被 bison 原封不动地复制到解析器代码文件中。它包含解析器调用的错误函数(yyerror)和调用解析器的主程序。

 void yyerror(const char *str)
 {
 fprintf(stderr," error: %s\n",str);
 }
 main()
 {
 yyparse();
 }

扩展解析器

您询问 expr 我怀疑它是 bison 的某些命令或内置功能。不清楚你在问什么，因为你从未澄清过这一点。然而，根据我的经验，许多学生得到了一个简单的解析器，就像你在一些 class 注释中说明的那样，并要求通过练习扩展它以识别包含算术表达式的行。这就是我要假设和解释的。

假设我们希望更改（或扩展）解析器以匹配简单的表达式，如 WORD + WORD 而不是单词行。

我们可以像这样重新定义规则 line：

 line:
 EOL { exit(1); }
 | expr EOL { printf("correct!\n"); }
 ;

规则 expr 是这样的：

expr :
     WORD '+' expr
     | WORD
     ;

如果我们的词法分析器匹配 NUMBER 而不是 WORD，我们甚至可以将它变成一个简单的计算器。（词法分析器在别处定义）。我们现在可以做这样的事情：

 line:
 EOL { exit(1); }
 | expr EOL { printf("expression value is = %d\n",); }
 ;

expr :
     NUMBER '+' expr { $$ =  +  ; }
     | NUMBER    {$$ =  )
     ;

进一步阅读

如果您想更进一步，我有几个小时的时间（不令人兴奋）YouTube video tutorials 来构建支持我的 classes 的简单解析器。他们可能会有所帮助。

非终结符号和符号规则解释，特别是 expr 保留？

non- terminal symbol and symbol rules explain and especially is the expr reserved?

c

bison

yacc