第3章 文法和语言(三)

2024-05-06 03:08
文章标签 语言 文法

本文主要是介绍第3章 文法和语言(三),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

五、文法的类型


(1)0型文法(短语文法):对任一产生式α→β,都有α∈(VN∪VT)+, β∈(VN∪VT)*

(2)1型文法(上下文有关文法):
   对任一产生式α→β,都有|β|≥|α|, 仅仅 S→ε除外。即α1Aα2→α1βα2(A在VN中,其他在V*中,β≠ε)
(3)2型文法(上下文无关文法):
    对任一产生式α→β,都有α∈VN , β∈(VN∪VT)*
  即A→β(A在VN中,β在V*中,)
(4)3型文法(正规文法):任一产生式α→β的形式都为A→aB或A→a,其中A∈VN ,B∈VN ,a∈VT


  • 例:1型(上下文有关)文法
   文法G[S]: S→aSBE
S→aBE
EB→BE
aB→ab
bB→bb
bE→be
eE→ee



  • 例:2型(上下文无关)文法
  
   文法G[S]: S→aB|bA
A→a|aS|bAA
B→b|bS|aBB
   文法G[S]: S→0A|1B|0
A→0A|1B|0S
B→1B|1|0


  • 例:定义标识符的3型(正规)文法
   文法G[I]: I → lT
I → l
T → lT
T → dT
T → l
T → d


文法和语言


  • 0型文法产生的语言称为0型语言
  • 1型文法或上下文有关文法( CSG )产生的语言称为1型语言或上下文有关语言(CSL)
  • 2型文法或上下文无关文法( CFG )产生的语言称为2型语言或上下文无关语言( CFL ) 
  • 3型文法或正则(正规)文法( RG )产生的语言称为3型语言或正则(正规)语言( RL )

六  上下文无关文法及其语法树

  • 上下文无关文法有足够的能力描述现今程序设计语言的语法结构。
  1. 算术表达式
  2. 语句
  • 赋值语句
  • 条件语句
  • 循环语句
  • ……

1、语法树与推导
  • 用于描述上下文无关文法的句型推导的直观方法
例: G[S]:
S→aAS
A→SbA
A→SS
S→a
A→ba



  • 叶子结点:树中没有子孙的结点。 从左到右读出推导树的叶子标记,所得的句型为推导树的结果。也把该推导树称为该句型的语法树。






3、二义文法

  • 若一个文法存在某个句子对应两棵不同的语法树,则称这个文法二义的。 或者,若一个文法存在某个句子有两个不同的最左(右)推导,则称这个文法二义的。
  • 产生某上下文无关语言的每一个文法都是二义的,则称此语言先天二义的。

排除文法二义性的两种方法:
(1)在语义上加些限制(如优先顺序和结合律)。
(2)重构无二义性的文法。



  • 练习:有文法G[N]:
                      N→SE|E
                      S →SD|D
                      E →0|2|4|6|8|10
                      D →0|1|2|3|4|5|6|7|8|9
(1)证明此文法有二义性
(2)此文法描述的语言是什么?
(3)试写出另一文法,其产生的语言和G[N]产生的语言等价且是无二义性的。




这篇关于第3章 文法和语言(三)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

C语言中自动与强制转换全解析

《C语言中自动与强制转换全解析》在编写C程序时,类型转换是确保数据正确性和一致性的关键环节,无论是隐式转换还是显式转换,都各有特点和应用场景,本文将详细探讨C语言中的类型转换机制,帮助您更好地理解并在... 目录类型转换的重要性自动类型转换(隐式转换)强制类型转换(显式转换)常见错误与注意事项总结与建议类型

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式,允

Android kotlin语言实现删除文件的解决方案

《Androidkotlin语言实现删除文件的解决方案》:本文主要介绍Androidkotlin语言实现删除文件的解决方案,在项目开发过程中,尤其是需要跨平台协作的项目,那么删除用户指定的文件的... 目录一、前言二、适用环境三、模板内容1.权限申请2.Activity中的模板一、前言在项目开发过程中,尤

C语言小项目实战之通讯录功能

《C语言小项目实战之通讯录功能》:本文主要介绍如何设计和实现一个简单的通讯录管理系统,包括联系人信息的存储、增加、删除、查找、修改和排序等功能,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录功能介绍:添加联系人模块显示联系人模块删除联系人模块查找联系人模块修改联系人模块排序联系人模块源代码如下

基于Go语言实现一个压测工具

《基于Go语言实现一个压测工具》这篇文章主要为大家详细介绍了基于Go语言实现一个简单的压测工具,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录整体架构通用数据处理模块Http请求响应数据处理Curl参数解析处理客户端模块Http客户端处理Grpc客户端处理Websocket客户端

使用SQL语言查询多个Excel表格的操作方法

《使用SQL语言查询多个Excel表格的操作方法》本文介绍了如何使用SQL语言查询多个Excel表格,通过将所有Excel表格放入一个.xlsx文件中,并使用pandas和pandasql库进行读取和... 目录如何用SQL语言查询多个Excel表格如何使用sql查询excel内容1. 简介2. 实现思路3

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求:新用户入职 创建一系列账号比较麻烦,打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ