软件设计师-上下文无关文法

1 什么是文法在编译原理中，文法（Grammar）是用于精确描述一种形式语言的规则集合。本题给出的是一个上下文无关文法，由以下要素组成：非终结符：S（可以继续推导的符号）终结符：x, y（最终句子中出现的实际字符）产生式：S → xSx | y（表示S可以替换成什么）2 产生式的含义S → xSx：递归规则，在S的外层左右各加一个xS → y：基础规则，递归结束，S直接变成y竖线 | 表示“或”，即有两种选择3 推导过程分析我们从起始符号S开始，逐步推导出所有可能的句子。3.1 基础推导（n=0）选择规则 S → y：S ⇒ y得到句子：y3.2 一次递归（n=1）先选 S → xSx，再选 S → y：S ⇒ xSx ⇒ xyx得到句子：xyx3.3 二次递归（n=2）先选两次 S → xSx，再选 S → y：S ⇒ xSx ⇒ xxSxx ⇒ xxyxx得到句子：xxyxx3.4 三次递归