common-lisp - 通用 Lisp : A good way to represent grammar rules?

Question

这是一个 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

操作:我想获取语法规则右侧的第一个符号。那我想知道:是终结符吗？是ε符号吗？如果它是一个非终结符，那么我想得到它的语法规则。

Answer 1

GRAIL(Lisp 中的语法)

Description of GRAIL

Slightly modified version of GRAIL with a function generator included

我从第二个链接中包含 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 格式(定语从句语法)

在 Paradigms of Artificial Intelligence Programming 中有一个确定从句文法的实现。 .从技术上讲，它是 Prolog，但在本书中全部实现为 Lisp。

Grammar of English in DCG Format as used in PAIP

DCG Parser

希望这可以帮助!