编译原理

2024-01-11 22:19| 来源: 网络整理| 查看: 265

在进行语法分析的时候，有时候会对这些词语的概念不清晰，这里我们就详细归纳总结一下。

一. 概念名字定义句型从文法的开始符号 S起，推导出来的任一文法符号串 α (α∈(VN∪VT)*), 即 S ⇒ * α,则称 α 是这个文法 G的一个句型句子从文法的开始符号 S起，推导出来的任一终结符号串 a (a∈(VT)*), 则称 a 是这个文法 G的一个句子；句子是不包含非终结符的句型短语如果 αβδ 是文法的一个句型，即 S ⇒* αβδ, 并且 A ⇒+ β,则称 β 是句型 αβδ 相对于非终结符 A 的短语直接短语如果 αβδ 是文法的一个句型，即 S ⇒* αβδ, 并且 A ⇒ β,则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。句柄最左直接短语素短语它是一个短语，要求至少包含一个终结符，并且除它自身之外不再包含其他素短语最左素短语最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象

可以看出这个里面，最需要理解的概念就是短语，其他大部分概念都是在短语基础上延伸的，从概念上可以看出：

短语是句型的一部分或者是整个句型。短语是相对于某个非终结符的，因为只有非终结符才能推导其他字符。如果是文法开始符号 S, 它对应的短语就是整个句型。如果某个短语 β 是非终结符一步推导的，即 A ⇒ β, 那么短语 β 就是直接短语，且它也是非终结符 A 的产生式。二. 例子

假设有一个文法

G: S -> a | b | (T) T -> TdS | S

针对文法的一个特定句型 (Sd(T)db) , 其推导过程如下:

S => (T) => (TdS) => (TdSdb) => (Sd(T)db)

这个句型 (Sd(T)db) 对应的 CFG 分析树如下：

短语.png

你会发现该句型 (Sd(T)db)，就是这棵树所有叶节点从左到右排列得到的字符串。这个也叫做这棵树的产出或者边缘。

那个这个句型 (Sd(T)db)有多少个短语呢？

还记得短语的定义么，S ⇒* αβδ，αβδ 代表句型就是这里的 (Sd(T)db) 。

如果 α 和 δ 是空串的话，那么 β 就是 (Sd(T)db)，那么 β 就是句型 (Sd(T)db)相对于非终结符 S(即开始符号)的短语。如果 α 和 δ 都是 ( 的话，那么 β 就是 Sd(T)db, 那么 β 就是句型 (Sd(T)db)相对于非终结符 T 的短语。

这样分析来看，CFG 分析树中每一个子树，它的叶节点从左到右排列得到的字符串都是该句型的一个短语。注意这里的子树指的是由子树的开始节点和它的直接子节点以及子子节点一起构成的树，这棵树所有叶节点从左到右排列得到的字符串才是短语。如果子树的直接子节点都是叶节点，即没有下一层节点了，这样的子树构成的短语就是直接短语。

因此这个句型 (Sd(T)db) :

短语 : S,(T),Sd(T),b,Sd(T)db,(Sd(T)db)

短语就看这个句型对应的CFG 分析树有几颗子树，有五颗子树再包含分析树自己，一共就有6个短语。

直接短语 : S,(T),b

直接短语是只有两层的子树，在这个图中只有三个。

句柄 : S

最左的直接短语，即 S

素短语：(T),b 最左素短语：(T) 三. 寻找分析树中短语算法(java)

算法非常简单，就是通过分析树的后序遍历，先将子树的叶节点从左到右排合并成字符串(即一个短语)，然后用它代表子树的根节点的值，再和与子树根节点同一层节点值合并，得到新的短语。就这样从分析树的最底层，一路合并到分析树的根节点，就能得到所有的短语了。

3.1 Symbol 类 /** * @author by xinhao 2021/8/11 * 表示文法中字母表中一个符号，包括终结符和非终结符 */ public class Symbol { // 表示符号的值 private final String label; // 是不是终结符 private final boolean isTerminator; public Symbol(String label, boolean isTerminator) { this.label = label; this.isTerminator = isTerminator; } public String getLabel() { return label; } public boolean isTerminator() { return isTerminator; } @Override public String toString() { return label; } } 3.2 Node 类 /** * @author by xinhao 2021/8/11 * 表示分析树的节点，和它的children 子节点一起构成一颗分析树 */ public class Node { // 节点的字符 private final Symbol symbol; // 子节点 private List children; public Node(Symbol symbol) { this.symbol = symbol; } public void addChild(Node node) { if (children == null) { children = new ArrayList(); } children.add(node); } // 获取对应位置的子节点 public Node getChildNode(int index) { if (children == null || index >= children.size()) { return null; } return children.get(index); } public Symbol getSymbol() { return symbol; } public List getChildren() { return children; } public void setChildren(List children) { this.children = children; } @Override public String toString() { return symbol.toString(); } } 3.3 getPhrase 方法 /** * 通过递归的方式，获取子树合成的短语。 * 这里返回 Symbol，是为了取巧偷懒的，为了方便判断素短语的。 * 正常情况下，应该返回子树合成的短语字符串。 * @return */ private static Symbol getPhrase(Node node, List phraseList, List directPhraseList, List plainPhraseList) { // 表示是叶节点 if (node.getChildren() == null) { return node.getSymbol(); } // 是否是直接短语 boolean isDirectPhrase = true; // 至少包含一个终结符 boolean leastOneTerminator = false; StringBuilder builder = new StringBuilder(); for (Node child : node.getChildren()) { // 子节点的 children 不是 null，那么表示子节点不是叶节点，那么这个 node 生成的短语就不是直接短语 if (child.getChildren() != null) { isDirectPhrase = false; } Symbol symbol = getPhrase(child, phraseList, directPhraseList, plainPhraseList); if (symbol.isTerminator()) { leastOneTerminator = true; } builder.append(symbol.getLabel()); } String phrase = builder.toString(); phraseList.add(phrase); if (isDirectPhrase) { directPhraseList.add(phrase); } // 至少包含一个终结符 if (leastOneTerminator) { boolean isAddPlainPhrase = true; for (String str : plainPhraseList) { if (phrase.contains(str)) { isAddPlainPhrase = false; break; } } if (isAddPlainPhrase) { plainPhraseList.add(phrase); } } return new Symbol(phrase, leastOneTerminator); }

通过递归的方法，获取短语列表 phraseList, 直接短语列表 directPhraseList 和素短语列表plainPhraseList。

3.4 例子 public static Node create() { Node one0 = new Node(new Symbol("S", false)); one0.addChild(new Node(new Symbol("(", true))); one0.addChild(new Node(new Symbol("T", false))); one0.addChild(new Node(new Symbol(")", true))); Node two1 = one0.getChildNode(1); two1.addChild(new Node(new Symbol("T", false))); two1.addChild(new Node(new Symbol("d", true))); two1.addChild(new Node(new Symbol("S", false))); Node three0 = two1.getChildNode(0); three0.addChild(new Node(new Symbol("T", false))); three0.addChild(new Node(new Symbol("d", true))); three0.addChild(new Node(new Symbol("S", false))); Node three2 = two1.getChildNode(2); three2.addChild(new Node(new Symbol("b", true))); Node four0 = three0.getChildNode(0); four0.addChild(new Node(new Symbol("S", false))); Node four2 = three0.getChildNode(2); four2.addChild(new Node(new Symbol("(", true))); four2.addChild(new Node(new Symbol("T", false))); four2.addChild(new Node(new Symbol(")", true))); return one0; } public static void main(String[] agrs) { Node node = create(); List phraseList = new ArrayList(); List directPhraseList = new ArrayList(); List plainPhraseList = new ArrayList(); getPhrase(node, phraseList, directPhraseList, plainPhraseList); System.out.println("短语：" + phraseList); System.out.println("直接短语: " + directPhraseList); System.out.println("句柄: " + directPhraseList.get(0)); System.out.println("素短语: " + plainPhraseList); System.out.println("最左素短语: " + plainPhraseList.get(0)); }

运行结果:

短语：[S, (T), Sd(T), b, Sd(T)db, (Sd(T)db)] 直接短语: [S, (T), b] 句柄: S 素短语: [(T), b] 最左素短语: (T)

【本文地址】

公司简介

联系我们