通用Lisp：表示语法规则的好方法？

Question

通用Lisp：表示语法规则的好方法？

common-lispgrammarcontext-free-grammarrepresentation

7

这是一个关于Common Lisp数据表示的问题。

如何表示语法是一个好的方式？所谓“好”，是指一种简单易懂的表示方法，我可以在没有太多麻烦的情况下操作该表示方法。该表示方法不必特别高效；其他属性（简单、易懂、可处理）对我来说更为重要。

以下是一个示例语法：

Session → Facts Question
Session → ( Session ) Session
Facts → Fact Facts
Facts → ε
Fact → ! STRING
Question → ? STRING

这个表示法应该允许操作表示法的代码轻松区分终端符号和非终端符号。

非终端符号：Session，Facts，Fact，Question

终端符号：(，)，ε，！，？

这个特定的语法使用括号符号，这与Common Lisp使用的括号符号冲突。有什么好的方法来处理它？

我希望我的代码能够识别空字符串ε的符号。有什么好的方法来表示空字符串ε的符号？

我希望我的代码能够区分语法规则的左侧和右侧。

以下是我想在表示法上执行的一些常见操作。

考虑这个规则：

A → u1u2...un

操作：我想要获取语法规则的右侧第一个符号。然后我想知道：它是终端符号吗？还是ε符号？如果它是非终端符号，那么我想获取它的语法规则。

- Roger Costello

3

我曾经很久以前为大学做过类似的东西，你可能会发现这些有趣：回溯解析器、递归下降LL(1)和LALR(1)。以下是链接：回溯解析器、递归下降LL(1)和LALR(1)。 - Cactus

谢谢！所以你将语法表示为关联列表。a-list的键表示语法规则的LHS，键的值表示RHS。终端符号由字符串表示，非终端符号由原子表示。这样正确吗？回想起来，您对自己的表示满意吗？如果您要重新开始，您会做些什么不同的事情吗？您如何表示空符号？插入符号（^）代表什么，例如E^？ - Roger Costello

1

在 E^ 中的插入符号只是代表 E'。回想起来，我应该使用 E*，因为星号似乎是 Lisp 领域中通常的修饰符字符。我无法对这三个解析器进行太多评估，因为我从未在实际项目中使用过它们，这只是在大学学习各种解析器算法时为了自我教育而做的。 - Cactus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gustav Bertram · Accepted Answer

GRAIL (Lisp语言中的语法分析器)

为防止第二个链接失效，我在此附上GRAIL的BNF：

<grail-list>  ::= "'(" {<grail-rule>} ")"
<grail-rule>  ::= <assignment> | <alternation>
<assignment>  ::= "(" <type> " ::= " <s-exp> ")"
<alternation> ::= "(" <type> " ::= " <type> {<type>} ")"
<s-exp>       ::= <symbol> | <nonterminal> | "(" {<s-exp>} ")"
<type>        ::= "#(" <type-name> ")"
<nonterminal> ::= "#(" {<arg-name> " "} <type-name> ")"
<type-name>   ::= <symbol>
<arg-name>    ::= <symbol>

DCG格式（确定性子句语法）

在人工智能编程范例中有一个确定性子句语法的实现。技术上它是Prolog，但在书中全部实现为Lisp。

希望这可以帮到您！