用SLR/LR/LALR解析引号

Question

我试图解析一个由空格分隔的列表，但可能包含必须作为文字处理的引号。所以我试着写一个语法并用我最喜欢的解析算法来解析它，但是我似乎不能正确地理解语法。

让它变得特别棘手的是，我必须处理" "" "情况，它应该被解释为一个带有两个引号的字符串，而"" ""应该是两个空字符串。

更糟糕的是，我必须处理单引号' '和* *括号内的注释。例如:允许使用' * ' " * ' "，这应该解析为*和* '。

这是完全不可能的，还是有语法可以做到？

我想出的最好的尝试(_表示空格)：

start -> argv $
argv -> argv _ term | term
term -> "" | '' | ** | "dqexpr" | 'sqexpr' | *comment* | expr
expr -> string without ", ', *, or _
dqexpr -> string without "
sqexpr -> string without '
comment -> string without *

但我不能用LR(1)/SLR(1)解析器在/SLR上工作。

我尝试的语法，对于没有注释的简单情况，只有一个引号类型：

START -> ARGV $
ARGV -> ARGV _ TERM
ARGV -> TERM
TERM -> q STRING q
TERM -> FREE
STRING -> STRING CHAR
CHAR -> ''
CHAR -> q
CHAR -> c
FREE -> FREE c
FREE -> c

在这里，''是epsilon；q表示引号，_表示空格，c表示任何其他字符。可以在http://jsmachines.sourceforge.net/machines/slr.html上使用在线工具尝试语法。

Answer 1

您尝试的语法中的STRING非终端是无用的(也就是说，它不能派生任何终端字符串)，因为它没有非递归的生成。因此，解析器生成器应该与TERM -> q STRING q产品一起丢弃它。(理想情况下，会生成这样的错误消息。)如果这是固定的，生产CHAR -> ''将产生一个歧义，因为一个STRING可以是任意数量的CHAR，而且您无法知道一个空字符串中有多少个epsilon。理想情况下，解析器生成器将提供有意义的错误消息，尽管可以看到，并不是所有的错误消息都是这样做的。

这可以通过简单地将CHAR -> ''更改为STRING -> ''来解决，这也将解决由于连接两个epsilon的模糊性而产生的冲突。剩下的是允许引用的STRING包含一个q，这与伪代码("dqexpr -> string without "")中的描述相矛盾。

如果目的是允许一个术语是引用字符串的连接，以便" "" "是有效的(不需要输入它的语义)，那么可以通过添加另一个非终端的迭代来完成：

QTERMS -> QTERM
QTERMS -> QTERMS QTERM
QTERM  -> q STRING q

并将TERM -> q STRING q改为TERM -> QTERM。

我怀疑愿望是shell字处理的一种简化形式，在这种形式中，" word“可以是任意数量术语的连接，因此不仅" "" "是一个合法单词，" "' '和"x"foo'y'也是如此。这允许在同一个单词："'"'"'中同时包含单引号和双引号。如果我们也假设注释等同于空白，那么我们将得到以下语法：

START -> ARGV $
ARGV -> WORD
ARGV -> ARGV WHITES WORD
WHITES -> WHITE
WHITES -> WHITES WHITE
WHITE -> _
WHITE -> star CSTRING star
WORD -> TERM
WORD -> WORD TERM
TERM -> c
TERM -> squote SQSTRING squote
TERM -> dquote DQSTRING dquote
SQSTRING -> ''
SQSTRING -> SQSTRING c
SQSTRING -> SQSTRING _
SQSTRING -> SQSTRING star
SQSTRING -> SQSTRING dquote
DQSTRING -> ''
DQSTRING -> DQSTRING c
DQSTRING -> DQSTRING _
DQSTRING -> DQSTRING star
DQSTRING -> DQSTRING squote
CSTRING  -> ''
CSTRING  -> CSTRING c
CSTRING  -> CSTRING _
CSTRING  -> CSTRING squote
CSTRING  -> CSTRING squote

您使用的SLR工具成功地使用上述语法生成解析器。

Answer 2

语法实际上应该与匹配的括号相同，因此您应该能够找到大量解析数学表达式的示例。

我不太清楚您的示例语法试图实现什么，但在您的term规则中包括"“、”‘和**“对我来说似乎很奇怪。尝试将其更改为如下内容：

expr -> string
expr -> ' string '
expr -> " string "