句型/句子/语言 旬型( sentential forn): 如果S=*→>,那么Q就是文法的旬型 可能既包含非终结符号,又包含终结符号; 以是空串 句子( sentence) 文法的句子就是不包含非终结符号的句型 语言 文法G的语言就是G的旬子的集合,记为L(G) W在L(G)中当且仅当W是G的包子,即S=*=>W
句型/句子/语言 • 句型（sentential form）： – 如果S=*=> α，那么α就是文法的句型 – 可能既包含非终结符号，又包含终结符号；可 以是空串 • 句子（sentence） – 文法的句子就是不包含非终结符号的句型 • 语言 – 文法G的语言就是G的句子的集合，记为L(G) – w在L(G)中当且仅当w是G的句子，即S=*=>w
语法分析树 ·推导的图形表示形式 根结点的标号时文法的开始符号 每个叶子结点的标号是非终结符号、终结符号或￡ 每个内部节点的标号是非终结符号。 每个内部结点表示某个产生式的一次应用 内部结点的标号为产生式头,结点的子结点从左到右是 生式的体 有时允许树的根不是开始符号(对应于某个短 语) ·树的叶子组成的序列是根的大法符号的句型 棵分析树可对应多个推导序列,但是分析树 和最左(右)推导序列之间具有一一对应关系
语法分析树 • 推导的图形表示形式 – 根结点的标号时文法的开始符号 – 每个叶子结点的标号是非终结符号、终结符号或ε – 每个内部节点的标号是非终结符号。 – 每个内部结点表示某个产生式的一次应用 • 内部结点的标号为产生式头，结点的子结点从左到右是 产生式的体 • 有时允许树的根不是开始符号（对应于某个短 语）。 • 树的叶子组成的序列是根的文法符号的句型 • 一棵分析树可对应多个推导序列，但是分析树 和最左（右）推导序列之间具有一一对应关系
语法分析树的例子 文法:E→E|E+E|E*E|(E)|id 句子:-(id+id E E) E 图43-(id+id)的 语法分析树
语法分析树的例子 • 文法： E → -E | E+E | E*E | (E) | id • 句子：-(id+id)
从推导序列构造分析树 ·很设有推导序列 -A=a1→>a,=> 算法 初始化:a1的分析树是标号为A的单个结点 假设已经构造出a1-X1X2…,X的分析树,且a1 到a1的推导是将X替换为β,那么在当前分析树 中找出第j个非结点,向这个结点增加构成β的 子结点。如果β=8,则增加一个标号为的子结 点
从推导序列构造分析树 • 假设有推导序列： – A=a1=>a2 => … => an • 算法： – 初始化：a1的分析树是标号为A的单个结点 – 假设已经构造出ai-1=X1X2…Xk的分析树，且ai-1 到a1的推导是将Xj替换为β，那么在当前分析树 中找出第j个非ε结点，向这个结点增加构成β的 子结点。如果β=ε，则增加一个标号为ε的子结 点）
构造分析树的例子 推导序列 E→>=>-(E)=>E+E)=>-(id+E)=>-id+id E E E (E) E E E (E、) (E.) E E E+ E E E 图4-4推导(4.8)的语法分析树序列
构造分析树的例子 • 推导序列： – E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)