c - 非终端符号和符号规则说明，尤其是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是很好的参考资料。首先要注意的是overall layout of bison code，如下所示：

%{

   序幕

%}

      野牛宣言

%%

      语法规则

%%

      结语




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

第二部分是bison declarations，介绍语法中使用的终止符，并可选地指示语法的开始规则。

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

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

语法规则

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

rule: sequence of TERMINALS and non terminals ;

按照惯例，TERMINAL名称使用大写，非终端名称则不使用。

一个例子：

declaration : ID ":" ID ;

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


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

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

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

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

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

带注释的示例

%{

   %{是`％{...}％对的开始，它标记要复制的代码
 放入野牛生成的C代码的序言。它允许声明
 以及要插入的导入。
  

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

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

 %}
 %token WORD
 %token EOL
 %%

   这是野牛声明部分，指示我们从词法分析器导入称为WORD和EOL的标记。
 词法分析器代码在其他地方定义，因此我们不知道这些标记表示什么字符序列。
 我们可以从他们的名字中猜出来！
 %%标记声明的结尾和规则部分的开始

 input:
 /* empty */

   这定义了称为input的规则（或非终止规则）。
 该规则仅包含注释，这实际上意味着空字符串或空文件是与称为输入的规则的有效匹配。这意味着允许解析器不解析任何内容！

 |
 input line

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

 input : input line

 ;

   分号;标记行的语法规则（非末尾）的结尾。
 上下文无关语法的知识将向我们表明，此规则与任意长度的可选行序列匹配。定义线的内容由后面的非终端“线”定义。

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

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

 words:
 words WORD
 | WORD
 ;

   这定义了非终结符称为单词，它是称为WORD的令牌/终结符的无限序列。

 %%

   这标志着野牛规则部分的结束。这之后所有的代码都将由bison不变地复制到解析器代码文件中。它包含由解析器（yyerror）调用的错误函数和调用解析器的主程序。

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

扩展解析器

您询问有关expr的信息，希望它是我怀疑的野牛的某些命令或内置功能。您不清楚要问什么，因为您从未澄清过这一点。但是，以我的经验来看，许多学生都得到了一个简单的解析器，就像您在某些课堂笔记中说明的那样，并通过练习要求将其扩展为识别包含算术表达式的行。这就是我要假设并解释的内容。

假设我们希望更改（或扩展）解析器以匹配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",$1); }
 ;

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

进一步阅读

如果您想走得更远，我会花几个小时（令人兴奋）YouTube video tutorials来构建支持我的类的简单解析器。他们可能会有所帮助。