语法匹配正则表达式字符 类，结尾破折号
Grammar matching regex character classes, trailing dash
我正在编写自己的 LALR(1) 解析器生成器，所以我不确定我的解析器生成器或语法是否有问题。
我正在尝试为正则表达式生成解析器。
我对字符 类 有以下规则（稍微简化）：
LBRACKET: "[" // the [ character
RBRACKET: "]"
DASH: "-"
CHAR: [^[\]] // everything except square brackets
class ::= LBRACKET class_contents RBRACKET
class_contents ::= class_element | class_element class_contents
class_element ::= literal | literal DASH literal
literal ::= DASH | CHAR
我可以匹配正则表达式，例如 [a-bc-d]，但我不能匹配 [a-bc-de-]，它应该对应于匹配字符 a, b, c, d, e, -.
的规则
似乎在看到标记 e（类型 literal）和 -（类型 DASH）后，解析器尝试匹配规则 literal DASH literal.
看到]（类型RBRACKET）后，需要意识到它启动了错误的生产。
这是不是解析器需要 2 个先行标记，所以 LALR(1) 不够用的情况？
在这种情况下，有没有办法重写语法使其起作用？
或者这个语法对匹配 [a-bc-de-] 是否有效，我应该在我的解析器生成器中寻找错误？
是的，LALR(1) 是不够的。 LALR(1) parser-generator 应该抱怨生产中的 shift-reduce 冲突：
class_element ::= literal | literal DASH literal
移动一个literal后，你进入一个状态，其内核是两个项目：
class_element ::= literal .
class_element ::= literal . DASH literal
分别需要reduce action和shift action，这不能通过1个lookahead符号解决，因为reduce action的follow set包括DASH。
而且前瞻的 2 个标记也不起作用。事实上，这个文法对于任何 k 都不是 LALR(k)，因为它是有歧义的：class_contents 可以用两种方式推导 literal DASH literal（三个 class_elements 或一个）。
In this case, is there a way to rewrite the grammar so that it works?
（抱歉，错过了原问题的那一部分。）
可以为这种语言创建明确的语法。您几乎肯定必须放弃 literal ::= DASH 生产。您可能 need/want 将 "literal DASH" 限制在 class 的末尾。例如，我认为这样做可以：
class_contents ::= DASH | class_element | class_element class_contents
class_element ::= literal | literal DASH literal
literal ::= CHAR
（您可以等效地将 "literal DASH" 限制为 class 的 start。允许两者是可能的，但可能不那么简单。）
虽然没有歧义，但这个语法仍然不是 LALR(1)：它与原始语法有相同的 shift-reduce 问题。但是，我认为它是 LALR(2)。
如果您真的想要 LALR(1)，有一个理论结果表明任何 LALR(k) 文法都可以转换为等效的 LALR(1) 文法。但我不确定结果会是什么样子。
请注意，问题 "Is LALR(1) sufficient?" 可能意味着：
"Can a LALR(1) parser(-generator) handle this grammar?"
或
"Is there a LALR(1) grammar that can express this language?"
我按顺序回答了这两个问题，但应该更清楚地区分它们。
LALR(1) 应该没问题。您只需要将 class_element 重写为 left-recursion，这在 LALR(1)
中通常更可取
class: LBRACKET class_contents RBRACKET
class_contents: class_element | class_element class_contents
class_element: literal | class_element DASH literal
literal: DASH | CHAR
我在以下输入上测试了这个语法，它似乎运行良好：
[a-bc-de-]
[a-bc-de]
[-a-bc-de]
[-]
如前所述，您的语法有歧义。虽然有时可以使用标准启发式方法（例如 "prefer shift to reduce"）解决歧义（显示为 shift/reduce 冲突），但这种技术并不完全通用，而且并不总是容易理解决议的后果。
实用的 LALR 生成器确实有解析算法，通常基于运算符优先级声明并回退到默认算法（更喜欢移位，如果没有移位，更喜欢语法中的第一个归约）。这些技术可以简化语法编写，有时还可以使语法更具可读性和解析速度。但是，一旦您离开了自动解析器冲突解决的舒适区，光芒就会开始消退。
创建明确的语法并不难，特别是如果您从对允许的句子的精确定义开始。在这里，我将为正则表达式字符 classes 使用 Posix 标准的简化版本，以便专注于允许尾部破折号作为字符的精确问题。从标准中删除：
归类元素 ([.ä.])
等价classes ([=œ=])
标准命名字符classes ([:alpha:])
否定 classes ([^…])
根据Posix，字符class中的-被视为普通字符"if it occurs first (after an initial ^, if any) or last in the list, or as an ending range point in a range expression."（另外，空字符classes 是不允许的；如果 ] 是 class 中的第一个字符，它也被视为普通字符。）下面，我（还）没有实现这三个中的第一个标准（列表中的第一个），专注于其他两个。这允许使用非常简单的语法，类似于 Michael Dyck 提供的语法：
/* I use bison syntax in order to be able to easily test the grammars */
class : '[' contents ']' /* See Note 1 */
contents: '-'
| unit
| unit contents
unit : CHAR
| CHAR '-' CHAR /* See Note 2 */
| CHAR '-' '-'
与 Michael 的语法一样，此语法是明确的 LALR(2)，这使得它在理论上很有趣但实际上几乎没有用，因为没有普遍可用的 LALR(2) 解析器生成器。您可以使用 GLR 或 Early 解析器对其进行解析，但也可以将 (LA)LR(k) 文法机械地转换为 (LA)LR(1) 文法 [注 3]。 （迈克尔也提到了这种结构。）
我在很多 SO 答案中都提到了这个事实，但这个语法实际上足够简单，可以手动进行转换，这可能会稍微更容易理解。
改造很简单。为了将 LR(k) 减少到 LR(1)，我们只需将每个减少向右移动 k-1 个标记。为此，对于每个文法符号 V（终端和 non-terminals），我们创建所有可能的 "delayed" 文法符号。每个这样的符号都具有 <sub>first</sub>V<sub>follow</sub> 的形式，其中 first 和 follow 是长度为 k-1 的序列，来自 FIRST<sub>k−1</sub> 和 FOLLOW<sub>k −1</sub>组V[注3]。新符号 <sub>first</sub>V<sub>follow</sub> 表示 V 的一个实例，它出现了 k−1输入流中较早的标记，但此时可以减少，因为现在有足够的信息来决定。
显然，这代表了语法的巨大 blow-up，尽管对于具有 k = 2 的简单语法来说，它或多或少是易于管理的。实际上，构建 (LA)LR(k) 解析器同样易于管理。此外，转换后的语法远非可读性，这是 grammar-based 解析器生成的一个关键特征。 （当然，如果转换是由计算机程序在后台完成的，那就没关系了。）但是这个构造确实证明了每个 (LA)LR(k) 文法都有一个等价的 (LA)LR(1 ) 语法。
完整的构建还展示了如何在解析树的构建过程中撤销转换。我还没有看到关于如何转换语义动作的描述，但是 yacc/bison 并不是很难。需要的是给每个（转换后的）符号两个属性（或者，用双音术语来说，一个 struct 由两个值组成）：一个表示（延迟的）符号被减少的语义值，另一个表示刚刚移动的标记的语义值。
在形式为 <sub>first</sub>V<sub>follow</sub> 的符号中，减少值是V的语义值，而延迟的token值是follow中最后一个token的语义值。 Yacc/bison 对 $i 语法实施 rarely-used 扩展，允许语义操作通过使用小于 1 的 i 值来引用值堆栈中较早出现的语义值. 使用这种机制，将在 $(i − (k−1)) 处找到与符号 $i 对应的代币值。 （因为i一定是常数，写规则的时候要自己做减法。）
在下面的示例中，我根本没有使用缩减值；相反，减少只是打印减少的价值。 [=37=] 等语义值引用是应用上述公式的结果。 （本例中k-1为1，所以[=37=]指的是right-hand这边位置1的符号的token值。）
有了这个，这里有一个完整的程序，你可以用它来测试语法：
$ cat charclass.y
%token CHAR
%code {
#include <ctype.h>
#include <stdio.h>
#include <string.h>
int yylex(void) {
int c;
do c = getchar(); while (c != '\n' && isspace(c));
yylval = c;
switch (c) {
case EOF: return 0;
case '\n': case '-': case '[': case ']': return c;
default: return CHAR;
}
}
void yyerror(const char* msg) {
fprintf(stderr, "%s\n", msg);
}
}
%%
input: %empty
| input class '\n'
| input '\n'
| error '\n' { yyerrok; }
/* Original untransformed grammar, for reference */
class: '[' contents ']'
contents: '-' | unit | unit contents
unit : CHAR | CHAR '-' CHAR | CHAR '-' '-'
*/
class : '[' OPEN-class-epsi { fputc('\n', stderr); }
OPEN-class-epsi : OPEN-OPEN-DASH DASH-contents-CLOS CLOS-CLOS-epsi
| OPEN-OPEN-CHAR CHAR-contents-CLOS CLOS-CLOS-epsi
DASH-contents-CLOS : DASH-DASH-CLOS { fprintf(stderr, "CHR(%c) ", [=11=]); }
CHAR-contents-CLOS : CHAR-unit-CLOS
| CHAR-unit-DASH DASH-contents-CLOS
| CHAR-unit-CHAR CHAR-contents-CLOS
CHAR-unit-CLOS : CHAR-CHAR-CLOS { fprintf(stderr, "CHR(%c) ", [=11=]); }
| CHAR-CHAR-DASH DASH-DASH-CHAR CHAR-CHAR-CLOS { fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
| CHAR-CHAR-DASH DASH-DASH-DASH DASH-DASH-CLOS { fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
CHAR-unit-DASH : CHAR-CHAR-DASH { $$ = ; fprintf(stderr, "CHR(%c) ", [=11=]); }
| CHAR-CHAR-DASH DASH-DASH-CHAR CHAR-CHAR-DASH { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
| CHAR-CHAR-DASH DASH-DASH-DASH DASH-DASH-DASH { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
CHAR-unit-CHAR : CHAR-CHAR-CHAR { $$ = ; fprintf(stderr, "CHR(%c) ", [=11=]); }
| CHAR-CHAR-DASH DASH-DASH-CHAR CHAR-CHAR-CHAR { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
| CHAR-CHAR-DASH DASH-DASH-DASH DASH-DASH-CHAR { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
CLOS-CLOS-epsi : %empty
CHAR-CHAR-CHAR : CHAR
CHAR-CHAR-CLOS : ']'
CHAR-CHAR-DASH : '-'
DASH-DASH-CHAR : CHAR
DASH-DASH-CLOS : ']'
DASH-DASH-DASH : '-'
OPEN-OPEN-DASH : '-'
OPEN-OPEN-CHAR : CHAR
%%
int main(int argc, char** argv) {
#if YYDEBUG
if (argc > 1 && strcmp(argv[1], "-d") == 0) yydebug = 1;
#endif
return yyparse();
}
这是一个简短的示例 运行:
$ bison -t -o charclass.c charclass.y && gcc -Wall -std=c11 -o charclass -ggdb charclass.c
$ ./charclass
[abc]
CHR(a) CHR(b) CHR(c)
[a-bc]
RNG(a-b) CHR(c)
[ab-c]
CHR(a) RNG(b-c)
[ab-]
CHR(a) CHR(b) CHR(-)
[a-b-]
RNG(a-b) CHR(-)
[a--]
RNG(a--)
[a---]
RNG(a--) CHR(-)
[a-b-c]
RNG(a-b) syntax error
研究野牛踪迹可能有帮助也可能没有帮助。 FWIW，这是一个例子：
$ ./charclass -d <<< '[a-b-]'
Starting parse
Entering state 0
Reading a token: Next token is token '[' ()
Reducing stack by rule 1 (line 23):
-> $$ = nterm input ()
Stack now 0
Entering state 2
Next token is token '[' ()
Shifting token '[' ()
Entering state 6
Reading a token: Next token is token CHAR ()
Shifting token CHAR ()
Entering state 8
Reducing stack by rule 29 (line 58):
= token CHAR ()
-> $$ = nterm OPEN-OPEN-CHAR ()
Stack now 0 2 6
Entering state 12
Reading a token: Next token is token '-' ()
Shifting token '-' ()
Entering state 19
Reducing stack by rule 24 (line 53):
= token '-' ()
-> $$ = nterm CHAR-CHAR-DASH ()
Stack now 0 2 6 12
Entering state 26
Reading a token: Next token is token CHAR ()
Shifting token CHAR ()
Entering state 31
Reducing stack by rule 25 (line 54):
= token CHAR ()
-> $$ = nterm DASH-DASH-CHAR ()
Stack now 0 2 6 12 26
Entering state 33
Reading a token: Next token is token '-' ()
Shifting token '-' ()
Entering state 19
Reducing stack by rule 24 (line 53):
= token '-' ()
-> $$ = nterm CHAR-CHAR-DASH ()
Stack now 0 2 6 12 26 33
Entering state 37
Reducing stack by rule 16 (line 45):
= nterm CHAR-CHAR-DASH ()
= nterm DASH-DASH-CHAR ()
= nterm CHAR-CHAR-DASH ()
RNG(a-b) -> $$ = nterm CHAR-unit-DASH ()
Stack now 0 2 6 12
Entering state 22
Reading a token: Next token is token ']' ()
Shifting token ']' ()
Entering state 14
Reducing stack by rule 26 (line 55):
= token ']' ()
-> $$ = nterm DASH-DASH-CLOS ()
Stack now 0 2 6 12 22
Entering state 16
Reducing stack by rule 8 (line 37):
= nterm DASH-DASH-CLOS ()
CHR(-) -> $$ = nterm DASH-contents-CLOS ()
Stack now 0 2 6 12 22
Entering state 29
Reducing stack by rule 10 (line 39):
= nterm CHAR-unit-DASH ()
= nterm DASH-contents-CLOS ()
-> $$ = nterm CHAR-contents-CLOS ()
Stack now 0 2 6 12
Entering state 20
Reducing stack by rule 21 (line 50):
-> $$ = nterm CLOS-CLOS-epsi ()
Stack now 0 2 6 12 20
Entering state 28
Reducing stack by rule 7 (line 36):
= nterm OPEN-OPEN-CHAR ()
= nterm CHAR-contents-CLOS ()
= nterm CLOS-CLOS-epsi ()
-> $$ = nterm OPEN-class-epsi ()
Stack now 0 2 6
Entering state 10
Reducing stack by rule 5 (line 34):
= token '[' ()
= nterm OPEN-class-epsi ()
-> $$ = nterm class ()
Stack now 0 2
Entering state 7
Reading a token: Next token is token '\n' ()
Shifting token '\n' ()
Entering state 13
Reducing stack by rule 2 (line 24):
= nterm input ()
= nterm class ()
= token '\n' ()
-> $$ = nterm input ()
Stack now 0
Entering state 2
Reading a token: Now at end of input.
Shifting token $end ()
Entering state 4
Stack now 0 2 4
Cleanup: popping token $end ()
Cleanup: popping nterm input ()
我依赖于 S. Sippu 和 E 的 Parsing Theory 第 6.7 节中算法的描述：Soisalon-Soininen (Springer-Verlag, 1988 ) 应该可以在任何好的学术图书馆找到。
备注：
bison，与许多解析器生成器一样，允许您用单引号编写 single-character 标记，恕我直言，这使语法更具可读性。
为了简化后面的步骤，我避免定义
任意：CHAR | '-'
可以用来允许 - 作为 "ending range point"（如 %--）。 (unit: CHAR '-' any)。相反，我写了两个 unit 规则，有效地扩展了上面的 any 产生式。
下面描述的转换将 LR(k) 文法转换为 LR(1) 文法，或将 LALR(k) 文法转换为 LALR(1) 文法。我用(LA)LR(k)作为short-hand来表示这两种情况；这是不精确的，因为转换还将 SLR(k) 文法转换为 SLR(1) 文法。
这里的例子中 k-1 是 1 并且没有 epsilon 产生式，所以我们可以简单地使用 FIRST 集作为文法符号。但在一般情况下，给定符号 V 的推导可能比 k-1 短。更精确的表述是 follow 是 FOLLOW<sub>k−1</sub>(V) 中的一个元素，而 first 是一个FIRST<sub>k−1</sub>(V # follow)中的元素，使用#作为连接运算符。
我正在编写自己的 LALR(1) 解析器生成器，所以我不确定我的解析器生成器或语法是否有问题。
我正在尝试为正则表达式生成解析器。 我对字符 类 有以下规则（稍微简化）：
LBRACKET: "[" // the [ character
RBRACKET: "]"
DASH: "-"
CHAR: [^[\]] // everything except square brackets
class ::= LBRACKET class_contents RBRACKET
class_contents ::= class_element | class_element class_contents
class_element ::= literal | literal DASH literal
literal ::= DASH | CHAR
我可以匹配正则表达式，例如 [a-bc-d]，但我不能匹配 [a-bc-de-]，它应该对应于匹配字符 a, b, c, d, e, -.
似乎在看到标记 e（类型 literal）和 -（类型 DASH）后，解析器尝试匹配规则 literal DASH literal.
看到]（类型RBRACKET）后，需要意识到它启动了错误的生产。
这是不是解析器需要 2 个先行标记，所以 LALR(1) 不够用的情况？
在这种情况下，有没有办法重写语法使其起作用？
或者这个语法对匹配 [a-bc-de-] 是否有效，我应该在我的解析器生成器中寻找错误？
是的，LALR(1) 是不够的。 LALR(1) parser-generator 应该抱怨生产中的 shift-reduce 冲突：
class_element ::= literal | literal DASH literal
移动一个literal后，你进入一个状态，其内核是两个项目：
class_element ::= literal .
class_element ::= literal . DASH literal
分别需要reduce action和shift action，这不能通过1个lookahead符号解决，因为reduce action的follow set包括DASH。
而且前瞻的 2 个标记也不起作用。事实上，这个文法对于任何 k 都不是 LALR(k)，因为它是有歧义的：class_contents 可以用两种方式推导 literal DASH literal（三个 class_elements 或一个）。
In this case, is there a way to rewrite the grammar so that it works?
（抱歉，错过了原问题的那一部分。）
可以为这种语言创建明确的语法。您几乎肯定必须放弃 literal ::= DASH 生产。您可能 need/want 将 "literal DASH" 限制在 class 的末尾。例如，我认为这样做可以：
class_contents ::= DASH | class_element | class_element class_contents
class_element ::= literal | literal DASH literal
literal ::= CHAR
（您可以等效地将 "literal DASH" 限制为 class 的 start。允许两者是可能的，但可能不那么简单。）
虽然没有歧义，但这个语法仍然不是 LALR(1)：它与原始语法有相同的 shift-reduce 问题。但是，我认为它是 LALR(2)。
如果您真的想要 LALR(1)，有一个理论结果表明任何 LALR(k) 文法都可以转换为等效的 LALR(1) 文法。但我不确定结果会是什么样子。
请注意，问题 "Is LALR(1) sufficient?" 可能意味着：
"Can a LALR(1) parser(-generator) handle this grammar?"
或
"Is there a LALR(1) grammar that can express this language?"
我按顺序回答了这两个问题，但应该更清楚地区分它们。
LALR(1) 应该没问题。您只需要将 class_element 重写为 left-recursion，这在 LALR(1)
class: LBRACKET class_contents RBRACKET
class_contents: class_element | class_element class_contents
class_element: literal | class_element DASH literal
literal: DASH | CHAR
我在以下输入上测试了这个语法，它似乎运行良好：
[a-bc-de-]
[a-bc-de]
[-a-bc-de]
[-]
如前所述，您的语法有歧义。虽然有时可以使用标准启发式方法（例如 "prefer shift to reduce"）解决歧义（显示为 shift/reduce 冲突），但这种技术并不完全通用，而且并不总是容易理解决议的后果。
实用的 LALR 生成器确实有解析算法，通常基于运算符优先级声明并回退到默认算法（更喜欢移位，如果没有移位，更喜欢语法中的第一个归约）。这些技术可以简化语法编写，有时还可以使语法更具可读性和解析速度。但是，一旦您离开了自动解析器冲突解决的舒适区，光芒就会开始消退。
创建明确的语法并不难，特别是如果您从对允许的句子的精确定义开始。在这里，我将为正则表达式字符 classes 使用 Posix 标准的简化版本，以便专注于允许尾部破折号作为字符的精确问题。从标准中删除：
归类元素 (
[.ä.])等价classes (
[=œ=])标准命名字符classes (
[:alpha:])否定 classes (
[^…])
根据Posix，字符class中的-被视为普通字符"if it occurs first (after an initial ^, if any) or last in the list, or as an ending range point in a range expression."（另外，空字符classes 是不允许的；如果 ] 是 class 中的第一个字符，它也被视为普通字符。）下面，我（还）没有实现这三个中的第一个标准（列表中的第一个），专注于其他两个。这允许使用非常简单的语法，类似于 Michael Dyck 提供的语法：
/* I use bison syntax in order to be able to easily test the grammars */
class : '[' contents ']' /* See Note 1 */
contents: '-'
| unit
| unit contents
unit : CHAR
| CHAR '-' CHAR /* See Note 2 */
| CHAR '-' '-'
与 Michael 的语法一样，此语法是明确的 LALR(2)，这使得它在理论上很有趣但实际上几乎没有用，因为没有普遍可用的 LALR(2) 解析器生成器。您可以使用 GLR 或 Early 解析器对其进行解析，但也可以将 (LA)LR(k) 文法机械地转换为 (LA)LR(1) 文法 [注 3]。 （迈克尔也提到了这种结构。）
我在很多 SO 答案中都提到了这个事实，但这个语法实际上足够简单，可以手动进行转换，这可能会稍微更容易理解。
改造很简单。为了将 LR(k) 减少到 LR(1)，我们只需将每个减少向右移动 k-1 个标记。为此，对于每个文法符号 V（终端和 non-terminals），我们创建所有可能的 "delayed" 文法符号。每个这样的符号都具有 <sub>first</sub>V<sub>follow</sub> 的形式，其中 first 和 follow 是长度为 k-1 的序列，来自 FIRST<sub>k−1</sub> 和 FOLLOW<sub>k −1</sub>组V[注3]。新符号 <sub>first</sub>V<sub>follow</sub> 表示 V 的一个实例，它出现了 k−1输入流中较早的标记，但此时可以减少，因为现在有足够的信息来决定。
显然，这代表了语法的巨大 blow-up，尽管对于具有 k = 2 的简单语法来说，它或多或少是易于管理的。实际上，构建 (LA)LR(k) 解析器同样易于管理。此外，转换后的语法远非可读性，这是 grammar-based 解析器生成的一个关键特征。 （当然，如果转换是由计算机程序在后台完成的，那就没关系了。）但是这个构造确实证明了每个 (LA)LR(k) 文法都有一个等价的 (LA)LR(1 ) 语法。
完整的构建还展示了如何在解析树的构建过程中撤销转换。我还没有看到关于如何转换语义动作的描述，但是 yacc/bison 并不是很难。需要的是给每个（转换后的）符号两个属性（或者，用双音术语来说，一个 struct 由两个值组成）：一个表示（延迟的）符号被减少的语义值，另一个表示刚刚移动的标记的语义值。
在形式为 <sub>first</sub>V<sub>follow</sub> 的符号中，减少值是V的语义值，而延迟的token值是follow中最后一个token的语义值。 Yacc/bison 对 $i 语法实施 rarely-used 扩展，允许语义操作通过使用小于 1 的 i 值来引用值堆栈中较早出现的语义值. 使用这种机制，将在 $(i − (k−1)) 处找到与符号 $i 对应的代币值。 （因为i一定是常数，写规则的时候要自己做减法。）
在下面的示例中，我根本没有使用缩减值；相反，减少只是打印减少的价值。 [=37=] 等语义值引用是应用上述公式的结果。 （本例中k-1为1，所以[=37=]指的是right-hand这边位置1的符号的token值。）
有了这个，这里有一个完整的程序，你可以用它来测试语法：
$ cat charclass.y
%token CHAR
%code {
#include <ctype.h>
#include <stdio.h>
#include <string.h>
int yylex(void) {
int c;
do c = getchar(); while (c != '\n' && isspace(c));
yylval = c;
switch (c) {
case EOF: return 0;
case '\n': case '-': case '[': case ']': return c;
default: return CHAR;
}
}
void yyerror(const char* msg) {
fprintf(stderr, "%s\n", msg);
}
}
%%
input: %empty
| input class '\n'
| input '\n'
| error '\n' { yyerrok; }
/* Original untransformed grammar, for reference */
class: '[' contents ']'
contents: '-' | unit | unit contents
unit : CHAR | CHAR '-' CHAR | CHAR '-' '-'
*/
class : '[' OPEN-class-epsi { fputc('\n', stderr); }
OPEN-class-epsi : OPEN-OPEN-DASH DASH-contents-CLOS CLOS-CLOS-epsi
| OPEN-OPEN-CHAR CHAR-contents-CLOS CLOS-CLOS-epsi
DASH-contents-CLOS : DASH-DASH-CLOS { fprintf(stderr, "CHR(%c) ", [=11=]); }
CHAR-contents-CLOS : CHAR-unit-CLOS
| CHAR-unit-DASH DASH-contents-CLOS
| CHAR-unit-CHAR CHAR-contents-CLOS
CHAR-unit-CLOS : CHAR-CHAR-CLOS { fprintf(stderr, "CHR(%c) ", [=11=]); }
| CHAR-CHAR-DASH DASH-DASH-CHAR CHAR-CHAR-CLOS { fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
| CHAR-CHAR-DASH DASH-DASH-DASH DASH-DASH-CLOS { fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
CHAR-unit-DASH : CHAR-CHAR-DASH { $$ = ; fprintf(stderr, "CHR(%c) ", [=11=]); }
| CHAR-CHAR-DASH DASH-DASH-CHAR CHAR-CHAR-DASH { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
| CHAR-CHAR-DASH DASH-DASH-DASH DASH-DASH-DASH { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
CHAR-unit-CHAR : CHAR-CHAR-CHAR { $$ = ; fprintf(stderr, "CHR(%c) ", [=11=]); }
| CHAR-CHAR-DASH DASH-DASH-CHAR CHAR-CHAR-CHAR { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
| CHAR-CHAR-DASH DASH-DASH-DASH DASH-DASH-CHAR { $$ = ; fprintf(stderr, "RNG(%c-%c) ", [=11=], ); }
CLOS-CLOS-epsi : %empty
CHAR-CHAR-CHAR : CHAR
CHAR-CHAR-CLOS : ']'
CHAR-CHAR-DASH : '-'
DASH-DASH-CHAR : CHAR
DASH-DASH-CLOS : ']'
DASH-DASH-DASH : '-'
OPEN-OPEN-DASH : '-'
OPEN-OPEN-CHAR : CHAR
%%
int main(int argc, char** argv) {
#if YYDEBUG
if (argc > 1 && strcmp(argv[1], "-d") == 0) yydebug = 1;
#endif
return yyparse();
}
这是一个简短的示例 运行:
$ bison -t -o charclass.c charclass.y && gcc -Wall -std=c11 -o charclass -ggdb charclass.c
$ ./charclass
[abc]
CHR(a) CHR(b) CHR(c)
[a-bc]
RNG(a-b) CHR(c)
[ab-c]
CHR(a) RNG(b-c)
[ab-]
CHR(a) CHR(b) CHR(-)
[a-b-]
RNG(a-b) CHR(-)
[a--]
RNG(a--)
[a---]
RNG(a--) CHR(-)
[a-b-c]
RNG(a-b) syntax error
研究野牛踪迹可能有帮助也可能没有帮助。 FWIW，这是一个例子：
$ ./charclass -d <<< '[a-b-]'
Starting parse
Entering state 0
Reading a token: Next token is token '[' ()
Reducing stack by rule 1 (line 23):
-> $$ = nterm input ()
Stack now 0
Entering state 2
Next token is token '[' ()
Shifting token '[' ()
Entering state 6
Reading a token: Next token is token CHAR ()
Shifting token CHAR ()
Entering state 8
Reducing stack by rule 29 (line 58):
= token CHAR ()
-> $$ = nterm OPEN-OPEN-CHAR ()
Stack now 0 2 6
Entering state 12
Reading a token: Next token is token '-' ()
Shifting token '-' ()
Entering state 19
Reducing stack by rule 24 (line 53):
= token '-' ()
-> $$ = nterm CHAR-CHAR-DASH ()
Stack now 0 2 6 12
Entering state 26
Reading a token: Next token is token CHAR ()
Shifting token CHAR ()
Entering state 31
Reducing stack by rule 25 (line 54):
= token CHAR ()
-> $$ = nterm DASH-DASH-CHAR ()
Stack now 0 2 6 12 26
Entering state 33
Reading a token: Next token is token '-' ()
Shifting token '-' ()
Entering state 19
Reducing stack by rule 24 (line 53):
= token '-' ()
-> $$ = nterm CHAR-CHAR-DASH ()
Stack now 0 2 6 12 26 33
Entering state 37
Reducing stack by rule 16 (line 45):
= nterm CHAR-CHAR-DASH ()
= nterm DASH-DASH-CHAR ()
= nterm CHAR-CHAR-DASH ()
RNG(a-b) -> $$ = nterm CHAR-unit-DASH ()
Stack now 0 2 6 12
Entering state 22
Reading a token: Next token is token ']' ()
Shifting token ']' ()
Entering state 14
Reducing stack by rule 26 (line 55):
= token ']' ()
-> $$ = nterm DASH-DASH-CLOS ()
Stack now 0 2 6 12 22
Entering state 16
Reducing stack by rule 8 (line 37):
= nterm DASH-DASH-CLOS ()
CHR(-) -> $$ = nterm DASH-contents-CLOS ()
Stack now 0 2 6 12 22
Entering state 29
Reducing stack by rule 10 (line 39):
= nterm CHAR-unit-DASH ()
= nterm DASH-contents-CLOS ()
-> $$ = nterm CHAR-contents-CLOS ()
Stack now 0 2 6 12
Entering state 20
Reducing stack by rule 21 (line 50):
-> $$ = nterm CLOS-CLOS-epsi ()
Stack now 0 2 6 12 20
Entering state 28
Reducing stack by rule 7 (line 36):
= nterm OPEN-OPEN-CHAR ()
= nterm CHAR-contents-CLOS ()
= nterm CLOS-CLOS-epsi ()
-> $$ = nterm OPEN-class-epsi ()
Stack now 0 2 6
Entering state 10
Reducing stack by rule 5 (line 34):
= token '[' ()
= nterm OPEN-class-epsi ()
-> $$ = nterm class ()
Stack now 0 2
Entering state 7
Reading a token: Next token is token '\n' ()
Shifting token '\n' ()
Entering state 13
Reducing stack by rule 2 (line 24):
= nterm input ()
= nterm class ()
= token '\n' ()
-> $$ = nterm input ()
Stack now 0
Entering state 2
Reading a token: Now at end of input.
Shifting token $end ()
Entering state 4
Stack now 0 2 4
Cleanup: popping token $end ()
Cleanup: popping nterm input ()
我依赖于 S. Sippu 和 E 的 Parsing Theory 第 6.7 节中算法的描述：Soisalon-Soininen (Springer-Verlag, 1988 ) 应该可以在任何好的学术图书馆找到。
备注：
bison，与许多解析器生成器一样，允许您用单引号编写 single-character 标记，恕我直言，这使语法更具可读性。
为了简化后面的步骤，我避免定义
任意：CHAR | '-'
可以用来允许
-作为 "ending range point"（如%--）。 (unit: CHAR '-' any)。相反，我写了两个unit规则，有效地扩展了上面的any产生式。下面描述的转换将 LR(k) 文法转换为 LR(1) 文法，或将 LALR(k) 文法转换为 LALR(1) 文法。我用
(LA)LR(k)作为short-hand来表示这两种情况；这是不精确的，因为转换还将 SLR(k) 文法转换为 SLR(1) 文法。这里的例子中
k-1是 1 并且没有 epsilon 产生式，所以我们可以简单地使用FIRST集作为文法符号。但在一般情况下，给定符号V的推导可能比k-1短。更精确的表述是follow是FOLLOW<sub>k−1</sub>(V)中的一个元素，而first是一个FIRST<sub>k−1</sub>(V # follow)中的元素，使用#作为连接运算符。