编译原理学习（三）--语法分析树

我就是我 2022-05-24 06:57 528阅读 0赞

语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程。在具体理解语法分析树之前需要先理清楚一些基本概念：

①.产生式

用变量expr来表示表达式，用变量stmt表示语句，那么这个构造规则可以表示为：stmt--->if（expr）stmtelse stmt

其中的箭头（--->）可以读作“可以具有以下形式”，这样的规则称为产生式。

②.文法定义

![1336354697_4885.png][]

关于文法定义中的终结符和非终结符，就参看另外一篇转载的文章。

语法分析树：

![1336355071_4427.png][]

注释：零个终结符号组成的串称为空串，记为∈。

举例说明： 9 - 5 + 2的语法树

![1336355464_1025.png][]

分析：根节点的标号为list，即为文法开始的符号。得出文法产生式：

list ---> list + digit

根节点的子节点经过类似推导：

list ---> list - digit

list ---> digit

digit---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

一棵语法分析树的叶子节点从左向右构成了树的结果，也就是从根节点上的非终结符号推导得到的符号串：9 - 5 + 2

一句话：为一个给定的终结符号串构建一棵语法分析树的过程称为对该符号串进行语法分析

理解了以上的内容之后，可以尝试做一下龙书第二章的习题，以加深理解：

2.2.1： 考虑下面的上下文无关文法：  
S → SS+ | SS\* |a

1)试说明如何使用该文法生成串aa+a\*。

2)试为aa+a\*构造一个分析树。

3)该文法产生的语言是什么？

解答：

1)S => SS\* => SS+S\* => aa+a\*

2)

![1336358602_8289.png][]

3)以a为变量，+和\*为二元操作符的后缀表达式

2.2.2 下面的文法产生什么语言？

1)S→0S1|01

\{0n1n（n=1,2,…）\}

2) S→+SS|-SS|a

以a为变量，+和-为二元操作符的前缀表达式

3)S→S(S)S|ε

括号的匹配

4)S→aSbS|bSaS| ε

由相同数目的a、b组成的字符串，或者空串。

5)S→a|S+S|SS|S\*|(S)

以a为数据元素，具有合并、连接、闭包和括号操作符的表达式。a是表达式，若S是表达式则S+S（表达式的合并）、SS（表达式的串联）、S\*（表达式的闭包运算）都是表达式。

2.2.3 练习2.2.2中哪些文法具有二义性？

3、4、5具有二义性。

可通过画某个串的分析树来说明

[1336354697_4885.png]: https://img-my.csdn.net/uploads/201205/07/1336354697_4885.png
[1336355071_4427.png]: https://img-my.csdn.net/uploads/201205/07/1336355071_4427.png
[1336355464_1025.png]: https://img-my.csdn.net/uploads/201205/07/1336355464_1025.png
[1336358602_8289.png]: https://img-my.csdn.net/uploads/201205/07/1336358602_8289.png

发表评论取消回复

表情：

评论列表（有 0 条评论，528人围观）

还没有评论，来说两句吧...

相关阅读

相关【编译原理】语法分析之分析策略

1. 语法分析的目的构建一个解析树或语法树 1. 根：独特的符号，“< program >"或其他 2. 叶子：词法分析阶段的tokens序列 3. 树中的每个

╰半橙微兮°/ 2024年03月31日 14:21/ 0 赞/ 93 阅读

相关编译原理PL0语法分析实验1

语法分析程序与词法分析程序共同点语法分析程序又叫下推自动机，词法分析程序又叫有穷自动机。 1，待分析的简单语言的词法相同点：都是分析种别码不同点：词法分析器分

朱雀/ 2023年10月01日 08:52/ 0 赞/ 25 阅读

相关【编译原理】图灵机、词法分析和语法分析

图灵机、词法分析和语法分析图灵机词法分析 LA (scanner)的作用编辑器的作用汇编程序和编译器

小灰灰/ 2023年09月24日 17:49/ 0 赞/ 79 阅读

相关编译原理实验（三）——LR（0）语法分析

编译原理实验（三）——LR（0）语法分析实验要求参考程序实验结果程序输入

古城微笑少年丶/ 2023年05月30日 09:16/ 0 赞/ 18 阅读

相关编译原理教程_4 语法分析

> 文章原稿 > https://gitee.com/fakerlove/fundamentals-of-compiling 文章目录 4. 语法分析

╰半夏微凉°/ 2023年01月21日 11:17/ 0 赞/ 263 阅读

相关编译原理语法分析（文本输入）源程序

\include<stdio.h> \include<string.h> lrparser(); yucu(); statement(); expressi

朴灿烈づ我的快乐病毒、/ 2022年08月02日 10:47/ 0 赞/ 189 阅读

相关自顶向下语法分析——编译原理

编程学习-编译原理本语法分析是编译程序的核心功能之一。语法分析的作用是识别由词法分析给出的单词符号串是否是给定问法的正确句子（程序）。语法分析常用的方法可分为自顶向

以你之姓@/ 2022年06月06日 12:06/ 0 赞/ 443 阅读

相关语法分析-哈工大编译原理实验二

实验2语法分析实验目的 1．巩固对语法分析的基本功能和原理的认识。 2．通过对语法分析表的自动生成加深语法分析表的认识。 3．理解并处理语法分析中的异常和错误

妖狐艹你老母/ 2022年06月05日 06:05/ 0 赞/ 260 阅读

相关编译原理学习（三）--语法分析树

语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程。在具体理解语法分析树之前需要先理清楚一些基本概念： ①.产生式用变量expr来表示表达式，用变量

我就是我/ 2022年05月24日 06:57/ 0 赞/ 529 阅读

相关编译原理入门（四）——语法分析简介

编译器编译的第二步便是语法分析，废话不多说，继续看。语法分析：语法分析的主要任务是：从词法分析器输出的token序列中识别出各类短语，并

心已赠人/ 2022年05月09日 08:54/ 0 赞/ 219 阅读