【PL理论深化】(2) 语法分析 (Syntax) | 编程语言的语法结构:文法 | 语义结构 (Sematics)

本文主要是介绍【PL理论深化】(2) 语法分析 (Syntax) | 编程语言的语法结构:文法 | 语义结构 (Sematics),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 💬 写在前面:编程语言是由归纳法生成的程序的集合。定义属于该语言的程序的形式的规则,即编写程序的规则,称为编程语言的 语法分析 (syntax) 而定义属于该语言的程序的意义的规则称为 语义结构(semantics)。这两者都是归纳定义的。

目录

0x00 语法分析(syntax analysis)

0x01 编程语言的语法结构:文法(grammar)

0x02 语义结构(Semantics)


0x00 语法分析(syntax analysis)

下面是一个由整数和四则运算符所构成的整数表达式集合,即整数表达式语言。

比如,以下整数表达式属于该语言中的程序:

.

像上述那样,程序通常用一维字符串来编写。

但实际上,计算机程序具有树形的二维结构,例如字符串:

我们将程序表示为树结构:

对应于图 (a) 的程序:

而对应于图 (b) 的程序,将用字符串编写的一维程序转换为二维树结构的技术 ——

称为 语法分析 (syntax analysis) 或 解析 (parsing) 。

(我们不会详细讨论语法结构分析的方法,而是着重于程序的结构如何呈现为树形)

0x01 编程语言的语法结构:文法(grammar)

假设程序的结构以树形结构明确给出,

整数表达式语言的语法结构可以通过以下推导规则归纳定义:

编程语言的语法结构通常采用 文法 (grammar) ,而不是推理规则来定义。

整数表达式语言的语法结构用文法表示如下:

上述规则表示有 5 种方法可以生成整数表达式。

根据第一条规则,任意整数 (n) 都可以是一个整数表达式。

而其余的规则意味着,对于任意两个整数表达式 E_1E_2

可以用四则运算符连接它们,从而创建一个新的整数表达式。

.

由于归纳规则的特性,通过这五种有限规则,可以生成无限多个任意的整数表达式。

例如,整数表达式 1+(2*(3-4)) 就是这样创建的:

如果将证明树的上下颠倒,并强调树的结构,就得到了图 (A) 。

像这样通过归纳定义的编程语言的语法结构,具有生成二维程序的规则。

.

为了将二维结构清晰地写成一维形式,只需适当地使用括号,例如表达为  1+(2*(3-4)) 。

0x02 语义结构(Semantics

如果语法结构是定义编程语言中程序外观的规则。

那么 语义结构 (semantics) 则是决定程序执行意义的规则。

程序的含义可以有多种定义,但对于整数表达式而言,

以计算表达式得到的整数值来定义其含义是最自然的。

我们可以这样表达:"计算整数表达式 E 得到整数 n " 或者 "整数表达式 E 的含义是 n "。

E\Rightarrow n

.

例如,1+(2*(3-4))\Rightarrow -1 表示程序 1+(2*(3-4)) 的含义是等于 −1。

这里的 \Rightarrow 表示一个关于程序和整数之间的二元关系。

换言之,若将程序的集合表示为 \mathbb P,整数的集合表示为 \mathbb Z

\Rightarrow 是 \mathbb P \times \mathbb Z 的一个子集 (即 \Rightarrow \subseteq \mathbb P \times \mathbb Z),它定义了整数表达式的语义结构。

对于整数表达式,可以通过以下推理规则来定义集合 \Rightarrow :

.

第一条规则 (E-Num) 对于任意整数 n,表示 (n,n) 是集合 \Rightarrow 的元素。

这里,整数 n 的意义被定义为整数值 n

第二条规则 (E-Plus) 表示如果 (E_1, n_1)(E_2,n_2) 是 \Rightarrow 的元素,

则 (E_1 + E_2, n_1+n_2) 也是 \Rightarrow 的元素,其余规则类似地定义。

.

然而,对于除法,定义限定 n2 不为零时才有意义。

例如,根据上述规则定义的集合 \Rightarrow 包含元素 \big((1+2)(3/3), 3\big) 。

整数表达式 (1+2)(3/3) 的含义被定义为 3。

可以证明 \big((1+2)*(3/3), 3\big)  是集合 \Rightarrow 的元素如下所示:

.

相对地,有些表达式可能看起来是正确的,但实际上可能没有定义。

例如,整数表达式 (3*4)/\big((1*2)-(1+1)\big) 对于任何整数 n

都无法通过推理规则 (3*4)/\big((1*2)-(1+1)\big) \Rightarrow n 进行证明。

.

因为整个表达式涉及除法,如果要证明它,就只能应用规则 \textrm{E-Div}

但在这种情况下,由于分母计算结果为 0,因此无法应用 \textrm{ E-Div} 规则。

这说明,并非所有通过编程语言的语法结构定义的程序都具有执行的实际意义。

即使通过了编译器的语法分析阶段,仍可能存在无法正确执行的程序!

.

到目前为止,我们已经从定义推理规则的角度定义了语义结构,

但是也可以直接从程序执行规则的角度解释这些规则。

例如,规则 \textrm{E-Plus} 描述了计算表达式 E_1 + E_2  的过程。

我们首先递归地计算表达式 E_1E_2 的值,得到 n_1n_2

然后定义为将这两个整数相加的过程。

通过这种方式解释语义结构,证明树的生成过程就成为程序执行的过程,

并且通过将语义结构定义为递归函数,我们可以直接获得编程语言的解释器 (interpreter) 。

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.9.14
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限,本文有错误和不准确之处在所难免,本人也很想知道这些错误,恳望读者批评指正!

📜 参考资料 

- R. Neapolitan, Foundations of Algorithms (5th ed.), Jones & Bartlett, 2015.

- T. Cormen《算法导论》(第三版),麻省理工学院出版社,2009年。

- T. Roughgarden, Algorithms Illuminated, Part 1~3, Soundlikeyourself Publishing, 2018.

- J. Kleinberg&E. Tardos, Algorithm Design, Addison Wesley, 2005.

- R. Sedgewick&K. Wayne,《算法》(第四版),Addison-Wesley,2011

- S. Dasgupta,《算法》,McGraw-Hill教育出版社,2006。

- S. Baase&A. Van Gelder, Computer Algorithms: 设计与分析简介》,Addison Wesley,2000。

- E. Horowitz,《C语言中的数据结构基础》,计算机科学出版社,1993

- S. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008.

- A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974.

- M. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997.

- A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003. - A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983.

- E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997.

- R. Sedgewick, Algorithms in C: 第1-4部分(第三版),Addison-Wesley,1998

- R. Sedgewick,《C语言中的算法》。第5部分(第3版),Addison-Wesley,2002

这篇关于【PL理论深化】(2) 语法分析 (Syntax) | 编程语言的语法结构:文法 | 语义结构 (Sematics)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1087693

相关文章

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

《mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据》文章主要介绍了如何从.frm和.ibd文件恢复MySQLInnoDB表结构和数据,需要的朋友可以参... 目录一、恢复表结构二、恢复表数据补充方法一、恢复表结构(从 .frm 文件)方法 1:使用 mysq

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》:本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者

结构体和联合体的区别及说明

《结构体和联合体的区别及说明》文章主要介绍了C语言中的结构体和联合体,结构体是一种自定义的复合数据类型,可以包含多个成员,每个成员可以是不同的数据类型,联合体是一种特殊的数据结构,可以在内存中共享同一... 目录结构体和联合体的区别1. 结构体(Struct)2. 联合体(Union)3. 联合体与结构体的

PostgreSQL如何查询表结构和索引信息

《PostgreSQL如何查询表结构和索引信息》文章介绍了在PostgreSQL中查询表结构和索引信息的几种方法,包括使用`d`元命令、系统数据字典查询以及使用可视化工具DBeaver... 目录前言使用\d元命令查看表字段信息和索引信息通过系统数据字典查询表结构通过系统数据字典查询索引信息查询所有的表名可

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c