上下文无关语法

上下文无关文法(CFGs)是用来描述上下文无关语言．上下文无关语法是一组用于生成模式的递归规则字符串．上下文无关的语法可以描述这一切常规的语言还有更多，但他们无法描述所有可能的语言。

上下文无关语法在理论计算机科学、编译器设计和语言学等领域都有研究。用CFG来描述编程语言而且解析器项目编译器可以从上下文无关的语法自动生成。

两个解析树，描述生成字符串“x + y * z”的cfg。来源:上下文无关语法维基百科页面。

可以生成上下文无关的语法上下文无关语言．他们通过一组递归定义的变量来实现这一点，这些变量由一组生成规则相互定义。上下文无关语法之所以如此命名，是因为语法中的任何产生式规则都可以应用于任何上下文——它不依赖于任何其他符号，这些符号可能存在也可能不存在于应用了规则的给定符号周围。

上下文无关语法有以下组件:

• 一套终端符号它们是出现在语言/语法生成的字符串中的字符。终端符号从不出现在产生式规则的左侧，而总是出现在右侧。

• 一套非终结符号(或变量)，它们是可以由非终止符生成的终止符模式的占位符。这些符号总是出现在生产规则的左侧，尽管它们也可以包含在右侧。CFG生成的字符串将只包含非结束符符号集中的符号。

• 一套产生式规则它们是替换非终结符符号的规则。产生式规则有以下形式:变量 $\ rightarrow$变量和结束符的字符串。

• 一个开始的象征它是一个特殊的非终结符符号，出现在由语法生成的初始字符串中。

作为比较，上下文敏感的语法是否有生成规则，左边和右边都可以被a包围上下文终止符和非终止符。

按照以下步骤从上下文无关的语法创建字符串:^[1]

• 用开始符号开始字符串。

• 通过将开始符号替换为产品的右侧，将其中一个生成规则应用于左侧的开始符号。

• 重复在字符串中选择非结束符符号的过程，并用一些相应产品的右侧替换它们，直到所有非结束符都被结束符替换为止。注意，可能不是所有的生产规则都被使用。

与上下文无关的语法可以用四元素来描述元组 $(V， \Sigma, R, S)，$在哪里

• $V$是变量的有限集(非终结符);
• $\σ$是一个有限集 $（$不相交的 $V)$终结符号的;
• $R$是否一组生产规则，其中每个生产规则将一个变量映射到一个字符串 $s \in (V \cup \Sigma)*$；
• $年代$ $（$这是 $V)$这是一个开始符号。

提出一种语法，它将生成上下文无关的(也是规则的)语言，其中包含所有带有匹配括号的字符串。

---

有许多语法可以完成这项任务。这个解决方案是实现它的一种方法，但应该让您了解您的(可能不同的)解决方案是否也有效。

开始的象征 $\ rightarrow$年代
非结束符变量= $\ {(,) \}$
生产规则:

• 年代 $\ rightarrow$（ ）
• 年代 $\ rightarrow$党卫军
• 年代 $\ rightarrow$(年代)。 $_ \广场$

一种压缩生产规则的方法如下:

我们可以

年代 $\ rightarrow$（ ）
年代 $\ rightarrow$党卫军
年代 $\ rightarrow$(年代)

翻译成一行:S $\ rightarrow$() | ss | (s) | $\ε,$在哪里 $\ε$是一个空字符串。

下面是一个上下文无关的语法，它生成算术表达式(减法、加法、除法和乘法)^[1]．

• 开始符号= <表达式>

• 终端符号= $\{+， -， *， /， (，)， \text{number}\}，$其中“number”是任意数字

• 生产规则:

  1. <表达式> $\ rightarrow$数量
  2. <表达式> $\ rightarrow$(<表达式>)
  3. <表达式> $\ rightarrow$<表达式> + <表达式>
  4. <表达式> $\ rightarrow$<表达式> - <表达式>
  5. <表达式> $\ rightarrow$<表达式> * <表达式>
  6. <表达式> $\ rightarrow$<表达式> / <表达式>

这允许我们用乘法、加法、除法和减法构造我们想要的任何表达式。这些产生式规则告诉我们，任何操作(例如乘法)的结果也是一个表达式(表示为)。

使用上面的例子，说明推导以下表达式的步骤: $(4 + 5) * (2 - 6)$．注意，有许多方法可以做到这一点，但是下面的解决方案应该提供足够的指导来检查推导是否有效。

显示答案

<表达式> $\ rightarrow$4(使用规则1)
<表达式> $\ rightarrow$5(使用规则1)
<表达式> $\ rightarrow$4 + 5(使用规则3)
<表达式> $\ rightarrow$(4 + 5)(使用规则2)
<表达式> $\ rightarrow$2(使用规则1)
<表达式> $\ rightarrow$6(使用规则1)
<表达式> $\ rightarrow$2 - 6(使用规则4)
<表达式> $\ rightarrow$(2 - 6)(使用规则2)
<表达式> $\ rightarrow$(4 + 5) *(2 - 6)(使用规则5)

与上下文无关的语法可以建模为解析树．树的节点表示符号，边表示产生式规则的使用。树的叶子是最终结果(终端符号)，它组成了语法用特定的符号序列和生成规则生成的字符串。

下面的解析树表示用语法生成字符串“a + a - a”的两种方法

$A \右箭头A + A | A - A | A。$

歧义语法的示例——可以用多种方式生成相同的字符串^[２]

因为这个语法可以用多个解析树实现，以获得相同的结果字符串，所以被称为模棱两可的．

与上下文无关的语法可以通过下推自动机就像常规的语言可以由有限状态机．因为所有规则语言都可以由cfg生成，所以所有规则语言也可以由下推自动机生成。

任何可以生成的语言正则表达式可以由上下文无关的语法生成。

做到这一点的方法是使用常规语言，确定它的有限状态机，并编写遵循转换函数的生成规则。

• 上下文无关语言

• 下推自动机

• 有限状态机

• 常规的语言

1. 纳尔逊，R。上下文无关文法．检索自2016年6月11日https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/cfg.html
2. , J。Leftmostderivations．检索于2016年6月14日https://en.wikipedia.org/wiki/File:Leftmostderivations_jaredwf.png