grammar - 如何创建元语法？

Question

我目前正在学习句法分析。我正在尝试制作一个可以生成特定语法的元语法:

A ⇒ A '+' C | C ;  
C ⇒ C * Q ;  
C ⇒ Q ;  
Q ⇒ a | b | 'A' | "B" | "(" A ")" | <num> ;  
<num> ⇒ <Signed Int> | Float ;  
<Signed Int> ⇒ Signe Int ;  
Signe ⇒ '-' | '+' | ~eps~  
<Int> ⇒ Digit Int | Digit ;  
Digit ⇒ '1' | '2' | '3' | '4' | 5 | 6 | 7 | 8 | "9" | "0" ;  
Float ⇒ Int '.' Int ;  

哪里<>被忽略(即 <int> 与 int 相同)，单/双引号用于字符串， ~eps~是针对 epsilon 的。其他一切都被视为符号(无论是终结符还是非终结符)。

目前我有这样的东西:

S ⇒ left "⇒" right ";" | ε  
left ⇒ symb | "<"symb">"  
right ⇒ QP
Q ⇒ symb | """symb""" | "'"symb"'" | "<"symb">" | ε  
P ⇒ symb | '|' Q | ε  

但这对我来说感觉很不对劲，我不太确定该怎么做。有没有一种方法可以确定元语法？我该怎么做呢？

Answer 1

不错的开始。你真的应该定义 symb:

letter = "A" | "B" |  ...  | "Z" ;
symb = letter symb | letter ;

但是你的元语法只允许一种语法规则。为了允许多个规则，我想你想写:

 S = R S | ε ;
 R = left "⇒" right ";"

您可能对使用元语法来处理自身语法和其他语法的工具非常感兴趣。这篇小论文关于MetaII ，来自(准备好了吗？)1964 讨论了这个问题并展示了如何使用它构建编译器。这是一篇令人惊叹的论文，它会扭曲你的大脑(以一种好的方式!)

读完本文后，您会对元语法感到非常自在。 (我在 20 世纪 70 年代初就学会了使用它来构建编译器)。