使用 SLR/LR/LALR 解析器解析报价

Question

我正在尝试解析由 space 分隔的列表，但可能包含我必须将其视为文字的引号。所以我尝试编写一个语法并使用我最喜欢的解析算法对其进行解析，但我似乎无法正确理解语法。

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

更糟糕的是，我必须处理单引号 ' ' 和 * * 括起来的注释。像这样的东西： ' * ' " * ' " 是允许的，它应该解析为 * 和 * '.

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

我想出的最佳尝试（_ 表示 space）：

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) 解析器在 " "" " 上完成这项工作。

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

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 表示引号，_ 表示 space，c 任何其他字符。可以使用 http://jsmachines.sourceforge.net/machines/slr.html

上的在线工具尝试语法

Answer 1

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

我不太确定您的示例语法试图完成什么，但在您的 term 规则中包含“”、“”和 ** 对我来说似乎很奇怪。尝试将其更改为：

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

Answer 2

您尝试的语法中的 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' 也是。这允许在同一个词中同时包含单引号和双引号："'"'"'。如果我们还假设评论等同于 white-space，我们最终得到以下语法：

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 tool使用上述语法生成解析器。

使用 SLR/LR/LALR 解析器解析报价

Parsing Quotes using a SLR/LR/LALR Parser

compiler-construction

string

parsing