1. 编译原理 正则语言 二义文法 急~
这个没有一个好老师，自己咬文嚼字看懂是很累的
二义性文法
【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。
二义性文法会引起歧义，应尽量避免之！
G(E)：E -> E+E | E*E | (E) | i
这两种展开
E E
E + E E * E
i E * E E + E i
i i i i
都可以表示i+i*i
所以;文法具有二义性。
2. 学习“编译原理”有什么作用
编译原理内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。主要是讲怎么做程序的编译器。需要数学基础和很强的逻辑思维。编译原理里的字符闭包是指有限循环。关于闭包这些名词解释，你们的课程应该有离散数学吧？会有对这些概念的解释。编译原理这书啊。得花老大精力去看了。每一行都会是至关重要的。如果你漏看了哪一节，或许接下来看到的新字母就不知道是什么意思了。所以要反复看，反复用逻辑思维推敲。做习题，习题类型也就几种，做熟了就很简单
3. 编译原理、离散数学中闭包是什么意思
数学中是闭的集合,也就是集合和它的边界的并。集合e的全体聚点并上e称为e的闭包。关系的闭包运算时关系上的一元运算，它把给出的关系R扩充成一新关系R’，使R’具有一定的性质，且所进行的扩充又是最“节约”的。
比如自反闭包，相当于把关系R对角线上的元素全改成1，其他元素不变，这样得到的R’是自反的，且是改动次数最少的，即是最“节约”的。
4. NFA转DFA的子集构造(subset construction)算法
之前 学习编译原理的时候老师有讲过 子集构造法 ，当时我以为自己听懂了，信心满满。可是这两天我做了一些题目，发现自己实际上还是太嫩了，学习浮于表面。之后又重新看了龙书和虎书，对子集构造法有了更深层次的了解。特此发出一篇文章分享我的经验。
概念是我们学习编译原理的重中之重，虽然他很晦涩难懂，但我有必要将其放在最开始。
虎书的概念更偏向于理论化，我当时看的时候一头雾水，但是不要担心， 之后会一点一点解释的 。
首先 ，我们形式化定义 闭包如下：
现在 ，假设我们位于由 NFA 状态 组成的集合 中。从 中的状态出发，输入符号 ，将到达 NFA 新的状态集；我们称这个状态集为 ：
利用 能更形式化地写出 NFA 模拟算法。如果初态是 ，输入字符串是 ，则算法为：
有了 和 算法，就能构造出 DFA ， DFA 的状态 就是 。抽象而言，如果 则存在一条从 到 的标记为 的边。令 是字母表：
个人认为龙书的概念更加通俗易懂，但是由于没有数学公式的归纳，导致理论基础不扎实，有点慌。所以推荐两本书一起看。
首先，是概念：
接着，是算法：
很简单 ，如果开始于 的机器接收字符串 ，始于 的和始于与 接收的串相同 ， 并到达相同状态 ，且两个状态集 同为终态或者非终态 ，那么 是等价的。我们可以把指向 的连线全部指向 ，并删除 ，反之亦然。
NFA 转 DFA 知识总结就到这里，有什么问题请留言，有错误请批评指正，非常感谢您的阅读。
5. 编译原理学习ing（1）词法分析——符号和文法
学习编译原理，首先要理解词法分析的基础概念。它涉及字母表中的符号，如字符、字符串和字符运算（如空串、连接、幂运算、乘积以及闭包）。文法是核心，它由两个非交集的集合——终结符集和非终结符集——以及消配则映射规则组成，规则通过开始符号（来自非终结符集）生成字符串。
文法通常用G(Vn, Vt, P, S)表示，其中Vn和Vt分别代表非终结符集和终结符集，P是产生式集，S是开始符号。例如，一个简单的文法可以表示为A-≥a，这意味着A可以推导为字符a。在文法G的作用下，通过规则推导形成句型，最终得到终结符串——句子，即语言L(G)。文法的等价性意味着不同的文法可能产生相同的语言。
对于文法的分类，上下文无关文法（2型文法）和语法树是关键概念。语法树通过标记和规则描述推导过程，但可能存在二义性，即同一种文法可以产生不同语法树。短语、直接短语和句柄的概念在句型分析中至关重要，用于确认句子是否符合文法。
在词法分析中，通过正则表达式或正规式（正规卖或集）分析输入，将字符转化为tokens，这是程序识别和处理语言的第一步。确定有限自动机（DFA）和非确定有限自动机（NFA）是自动化识别过程的基础，它们以不同的规则描述输入字符的接受方式。NFA与DFA虽然有区别，但它们在识别能力上是等价的，拿棚任何NFA都可以转换为等价的DFA。
6. 编译原理有有符号un-1.u=un吗
编译程序把源程序翻译为目标程序。根据源程序的语言种类，翻译程序可以分为汇编程序与编译程序。与之相对，解释程序是对源程序进行解释执行的程序。相应的可以将高级语言分为
编译型 C/C++, Swift, etc.
解释型 Python, javascript, etc.
混合型 Java, etc.
本文重点放在编译程序的设计上。典型的编译程序具有 7 77 个逻辑部分
对源程序扫描一次被称为一遍 (pass)。典型的一遍扫描编译程序有如下形式
通常将中间代码生成前的分析部分称为编译器的前端，其后的综合部分则被称为后端。这样就把一个编译程序分为了与源语言相关和与目标机有关的两个独立的部分，降低了程序的耦合。假设 llvm 编译器 支持 M MM 种源语言到 N NN 种目标语言的编译
传统的编译器如 gcc 可能需要开发 M × N M \times NM×N 个不同的子模块。而 llvm 使用统一的中间语言 llvm Intermediate Representation 只需要 M MM 个前端与 N NN 个后端，大大降低了开发成本。
文法
设非空有穷集合 Σ \SigmaΣ 为一字母表，则其上的符号串为 ∀ s ∈ Σ ∗ \forall s \in \Sigma^*∀s∈Σ
∗
，其中 ∗ *∗ 表示集合的闭包。特别的记 Σ 0 = ε \Sigma^0 = {\varepsilon}Σ
0
=ε 为空串组成的集合。规则通常写作
U : : = x or U → x , ∣ U ∣ = 1 , ∣ x ∣ ≥ 0 U ::= x\text{ or }U\rightarrow x,\quad |U| = 1, |x| \ge 0U::=x or U→x,∣U∣=1,∣x∣≥0
其中左部 U UU 是符号，右部 x xx 是有穷符号串。规则的集合 P PP 即可确定一个文法 G GG
<程序> ::= <常量说明><变量说明><函数说明>
<常量说明> ::= {const<常量定义>;}
<常量定义> ::= int<标识符>=<整数>{,<标识符>=<整数>}|char<标识符>=<字符>{,<标识符>=<字符>}
<变量说明> ::= {<类型标识符><变量定义>;}
<变量定义> ::= <标识符>[<下标>]{,<标识符>[<下标>]}
<下标> ::= '['<无符号整数>']' // <无符号整数>表示数组元素的个数，其值需大于0
<函数说明> ::= {(<类型标识符>|void)<函数定义>}void<主函数>
<函数定义> ::= <标识符>'('<参数表>')'<复合语句>
<参数表> ::= [<类型标识符><标识符>{,<类型标识符><标识符>}]
<主函数> ::= main'('')'<复合语句>
<复合语句> ::= '{'<常量说明><变量说明>{<语句>}'}'
<语句> ::= <条件语句>|'{'{<语句>}'}'|<函数调用语句>;|<赋值语句>;|<读语句>;|<写语句>;|<返回语句>;|;
<条件语句> ::= <if语句>|<while语句>|<do语句>|<for语句>
<if语句> ::= if'('<条件>')'<语句>[else<语句>]
<while语句> ::= while'('<条件>')'<语句>
<do语句> ::= do<语句>while'('<条件>')'
<for语句> ::= for'('<标识符>=<表达式>;<条件>;<标识符>=<标识符><加法运算符><无符号整数>')'<语句>
<条件> ::= <表达式>[<关系运算符><表达式>] // 表达式为0条件为假，否则为真
<函数调用语句> ::= <标识符>'('[<表达式>{,<表达式>}]')'
<赋值语句> ::= <标识符>['['<表达式>']']=<表达式>
<读语句> ::= scanf'('<标识符>{,<标识符>}')'
<写语句> ::= printf'('<字符串>[,<表达式>]')'|printf'('<表达式>')'
<返回语句> ::= return['('<表达式>')']
<表达式> ::= [<加法运算符>]<项>{<加法运算符><项>} // [+|-]只作用于第一个<项>
<项> ::= <因子>{<乘法运算符><因子>}
<因子> ::= <标识符>['['<表达式>']']|'('<表达式>')'|<整数>|<字符>|<函数调用语句>
<整数> ::= [<加法运算符>]<无符号整数>
<标识符> ::= <字母>{<字母>|<数字>}
<无符号整数> ::= <非零数字>{<数字>}|0
<数字> ::= 0|<非零数字>
<非零数字> ::= 1|...|9
<字符> ::= '<加法运算符>'|'<乘法运算符>'|'<字母>'|'<数字>'
<字符串> ::= "{十进制编码为32,33,35-126的ASCII字符}"
<类型标识符> ::= int|char
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= <|<=|>|>=|!=|==
<字母> ::= _|a|...|z|A|...|Z
复制
上述文法使用扩充的 BNF 表示法进行描述
符号 定义 说明
∣ \vert∣ 或 作用域由括号限定
{ t } n m \{t\}^m_n{t}
n
m
将 t tt 重复连接 n ∼ m n \sim mn∼m 次 缺省时 m = ∞ , n = 0 m = \infin,\ n = 0m=∞, n=0
[ t ] [t][t] 符号串 t tt 可有可无 等价于 { t } 1 \{t\}^1{t}
1
( t ) (t)(t) 局部作用域 主要用于限定 ∣ \vert∣ 范围
相关概念有
概念 符号 定义 示例
识别符号 Z ZZ 文法中第一条规则的左部符号 <程序>
字汇表 V VV 文法中出现的全部符号 { <程序>, <常量说明>, …, 0, 1, … }
非终结符号集 V n V_nV
n
全部规则的左部组成的集合 { <程序>, <常量说明>, <变量说明>, … }
终结符号集 V t V_tV
t
V − V n V - V_nV−V
n
{ 0, 1, …, _, a, b, … }
设 U : : = u ∈ P U ::= u \in PU::=u∈P 则对于 ∀ x , y ∈ V ∗ \forall x, y \in V^*∀x,y∈V
∗
有直接推导 x U y ⇒ x u y xUy \Rightarrow xuyxUy⇒xuy 。如果 y ∈ V t ∗ y \in V_t^*y∈V
t
∗
则 x U y ⤃ x u y xUy\ ⤃\ xuyxUy ⤃ xuy 称为规范推导。直接推导序列 u 0 ⇒ u 1 ⇒ ⋯ ⇒ u n u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_nu
0
⇒u
1
⇒⋯⇒u
n
可简记为
{ u 0 ⇒ + u n n > 0 u 0 ⇒ ∗ u n n ≥ 0 \begin{cases} u_0 \mathop\Rightarrow\limits^+ u_n & n > 0\\ u_0 \mathop\Rightarrow\limits^* u_n & n \ge 0\\ \end{cases}{
u
0
⇒
+
u
n
u
0
⇒
∗
u
n
n
>
0
n
≥
0
进一步定义
句型 V ∗ ∋ x ⇐ ∗ Z V^* \ni x \mathop\Leftarrow\limits^* ZV
∗
∋x
⇐
∗
Z
句子 V t ∗ ∋ x ⇐ + Z V_t^* \ni x \mathop\Leftarrow\limits^+ ZV
t
∗
∋x
⇐
+
Z
语言 L ( G ) = { x ∣ x is sentence } L(G) = \{ x| x\text{ is sentence} \}L(G)={x∣x is sentence}
如果文法 G GG 和 G ′ G'G
′
有 L ( G ) = L ( G ′ ) L(G) = L(G')L(G)=L(G
′
) ，则称这两个文法等价。设 w = x u y w=xuyw=xuy 为一句型，称 u uu 为一个相对于 U ∈ V n U \in V_nU∈V
n
的
w ww 的短语 如果 Z ⇒ ∗ x U y ∧ U ⇒ + u Z \mathop\Rightarrow\limits^* xUy \land U \mathop\Rightarrow\limits^+ uZ
⇒
∗
xUy∧U
⇒
+
u
w ww 的简单短语 如果 u uu 是短语且 U ⇒ u U \mathop\Rightarrow\limits uU⇒u
句型的最左简单短语称为句柄。
二义性
文法 G GG 是二义性的，如果 ∃ x ∈ L ( G ) \exist x \in L(G)∃x∈L(G) 使下列条件之一成立
x xx 可以对应两颗不同的语法树
x xx 有两个不同的规范推导
7. 编译原理的正闭包与星闭包是什么意思
仔细分析你的文法
f->f*|a|b也就是说，写成正则表达式的话
f就是[ab]*
同样的t也是[ab]*
你的整个文法就是[ab]+
[ab\+]*第一个+是+closure，第二个+是符号+，所以用了\符号
个人感觉这个文法是有问题的，因为根本不需要用上下文无关文法表达，只需要正则表达式就可以了。
8. 编译原理的正闭包与星闭包是什么意思
正闭包除去空字符串，星闭包包含空字符串。