二、高级语言语法描述

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

二、高级语言语法描述

2023-05-04 06:12:30 来源：博客园

文法

上下文无关文法

(资料图片仅供参考)

\[\begin{align*}文法 G[S]=(V_N，V_T，P，S)=>\left\{\begin{aligned}V_N&:非终结符集合\\V_T&:终结符集合\\P&:产生式\\S&:文法开始符号\end{aligned}\right.\end{align*}\]

四种文法0型 —— 短语文法1型 —— 上下文有关文法2型 —— 上下文无关文法3型 —— 正则文法（$A \rightarrow B\alpha|\alpha$ (左线性) 或 $A \rightarrow \alpha B|\alpha$(右线性)）

文法化简

删除 $P\rightarrow P$ 形式的产生式
删除不能推导出终结符的产生式
删除在推导中永不使用的产生式

基本概念

句型：从文法开始符号开始，每步推导所得到的字符串 (包括0步推导)句子：仅含终结符的句型二义性文法：文法中存在某个句子对应两棵不同的语法树，或两种不同的最左推导或两种不同的最右推导最左推导：每次替换最左边非终结符最右推导：每次替换最右边非终结符直接推导：$\Rightarrow$间接推导：

一步或多步推导：$\stackrel{+}{\Rightarrow}$
零步或多步推导：$\stackrel{*}{\Rightarrow}$

语法树

子树：任意节点及其全部后继直接子树(树高为1)：一子树根只有直接后继短语：每棵子树的叶子直接短语：每棵直接子树的叶子句柄：某句型的最左直接短语(规范分析中最先被规约的子串)素短语：至少包含一个终结符且不包含更小素短语的短语

题型

1.根据文法描述语言

给出下列文法所描述的语言

$S \rightarrow aSbS|bSaS|ε$解：a的个数和b的个数相等的串的集合
$S \rightarrow aAb \quad A \rightarrow cA|ε$解：$L(G)=\{ac^nb|n \ge 0 \}$

2.根据语言设计文法

构造产生下列语言的文法

$ L(G)={a^n b^n|n \ge 0 }$解：$G[S]:$$S\rightarrow aSb|ε$
设计一个文法，语言是正奇数集合，允许以0开头解：$G[S]:$$S \rightarrow TA$$T \rightarrow TR|ε$$R \rightarrow 0|1|2|3|4|5|6|7|8|9$$A \rightarrow 1|3|5|7|9$
设计一个文法，语言是能被5整除的十进制数解：$G[S]:$$S \rightarrow TR|R$$T \rightarrow TA$$A \rightarrow 0|1|2|3|4|5|6|7|8|9$$T \rightarrow 1|2|3|4|5|6|7|8|9$$R \rightarrow 0|5$
设计一个文法，语言是正偶数集合，不允许以0开头解：$G[S]:$$S \rightarrow TR|B$$T \rightarrow TA$$T \rightarrow 1|2|3|4|5|6|7|8|9$$A \rightarrow 0|1|2|3|4|5|6|7|8|9$$R \rightarrow 0|2|4|6|8$$B \rightarrow 2|4|6|8$

3.证明文法二义性

$G[S]:S \rightarrow iSeS|iS|i$解：句子 $iiiei$ 对应两棵不同的语法树，故该文法是二义的
$G[T]: T \rightarrow()|(T)|TT|ε$解：
句子 $()$ 对应两棵不同的语法树，故该文法是二义的

关键词：