请遵守AGPL 3.0协议 本主题已开源于hexo-theme-wang
Toggle Menu

归档

Post Date
Post Update Date

编译原理:FIRST集和FOLLOW集

FIRST集

FIRST(X): 可以从X推导出的所有串首终结符构成的集合

如果X⇒∗εX \Rightarrow {}^* \varepsilon.那么 ε∈FIRST(X)\varepsilon \in FIRST(X)

例

1◯ E→TE′FIRST(E)={(,id}2◯ E′→+TE′∣εFIRST(E′)={+,ε}3◯ T→FT′FIRST(T)={(,id}4◯ T′→∗FT′∣εFIRST(T′)={∗,ε}5◯ F→(E)∣idFIRST(F)={(,id}\begin{align*} \textcircled{1} &\ E \to TE' & \text{FIRST}(E) &= \lbrace (, \text{id} \rbrace \\ \textcircled{2} &\ E' \to +TE' \mid \varepsilon & \text{FIRST}(E') &= \lbrace +, \varepsilon \rbrace \\ \textcircled{3} &\ T \to FT' & \text{FIRST}(T) &= \lbrace (, \text{id} \rbrace \\ \textcircled{4} &\ T' \to *FT' \mid \varepsilon & \text{FIRST}(T') &= \lbrace *, \varepsilon \rbrace \\ \textcircled{5} &\ F \to (E) \mid \text{id} & \text{FIRST}(F) &= \lbrace (, \text{id} \rbrace \end{align*}

算法

#学习 #记录 #编译原理
Post Date
Post Update Date

编译原理:LL(1)文法

S_文法

💡

S_文法(简单的确定性文法)

每个产生式的右部都以终结符开始

同一非终结符的各个候选式的首终结符都不同

S_文法不含ε\varepsilon产生式

#学习 #记录 #编译原理
Post Date
Post Update Date

编译原理:文法转换

文法转换

  1. 例

文法GS→aAd∣aBeA→cB→b输入abc 文法G\\ S \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ 输入 a b c

⚠

同一非终结符的多个候选式存在共同前缀,将导致回溯现象

#学习 #记录 #编译原理
Post Date
Post Update Date

编译原理:NFA转DFA

不知道写点什么,所以记一下,以防失忆

🤖

本文内容含AI生成内容

DFA

确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。

定义

一个 DFA 可以用一个五元组 (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F) 来表示,其中：

  • QQ 是一个有限的状态集合。
  • Σ\Sigma 是一个有限的输入符号集合。
  • δ\delta 是状态转移函数,它将 Q×ΣQ \times \Sigma 映射到 QQ。也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。
  • q0q_0 是初始状态,q0∈Qq_0 \in Q。
  • FF 是接受状态集合,F⊆QF \subseteq Q。
#学习 #记录 #编译原理
Post Date
Post Update Date

离散数学:格的基本概念

回顾

偏序关系

<A,≤><A,\leq>是偏序集:≤是A上自反,反对称,和传递关系(偏序).\leq 是A上自反,反对称,和传递关系(偏序).

偏序集中的元素间的次序可以通过它的Hasse图反映出来. 偏序集中的元素间的次序可以通过它的Hasse图反映出来.

偏序集中的重要元素:极大(小)元,最大(小)元,上(下)界,上(下)确界.偏序集中的重要元素:极大(小)元,最大(小)元,上(下)界,上(下)确界.

#学习 #记录 #离散数学
Post Date
Post Update Date

离散数学:环与域

环定义

给定代数系统<A,+,∗>,+和∗是A上的二元运算,若满足下面条件<A,+,*>,+和*是A上的二元运算,若满足下面条件

(1)<A,+>是交换群(1) <A,+>是交换群

(2)<A,∗>是半群(2) <A,*>是半群

(3)∗对+可分配.即对任何a,b,c∈A,有a∗(b+c)=(a∗b)+(a∗c)及(a+b)∗c=(a∗c)+(b∗c)*对+可分配.即对任何a,b,c \in A ,有\\a*(b+c)=(a*b)+(a*c)及(a+b)*c=(a*c)+(b*c)

则称<A,+,∗><A,+,*>是环

#学习 #记录 #离散数学
Post Date
Post Update Date

离散数学:子群的陪集及拉格朗日定理

子群的陪集

定义

设<H,∗><H,*>是群<G,∗><G,*>的子群,a∈Ga \in G,定义集合

aH={a∗h∣h∈H}aH=\{a*h|h \in H\}

Ha={h∗a∣h∈H}Ha=\{h*a |h \in H\}

则称aH(Ha)为a确定的H在G中的左(右)陪集.

#学习 #记录 #离散数学
Post Date
Post Update Date

离散数学:子群及其证明

子群的定义

设<G,∗><G,*>是群,S是G的非空子集,如果<S,∗><S,*>满足:

(1) 对 ∀a,b∈S\forall a,b \in S均有a∗b∈Sa*b \in S (封闭性)

(2) 幺元e∈Se \in S (有幺元)

(3) 对 ∀a∈S\forall a \in S ,有a−1∈Sa^{-1} \in S (可逆)

💡

显而易见,结合性不证自明,略

则称<S,∗><S,*>是<G,∗><G,*>的子群

#学习 #记录 #离散数学
Post Date
Post Update Date

离散数学:群的定义及性质

定义

设<G,∗><G,*>是代数系统,如果∗*在G上满足**封闭性,可结合性,<G,∗><G,*>中有幺元,且G中每一个元素均可逆

则称<G,∗><G,*>是群

细分定义

(1)设<G,∗><G,*>是群,若集合G是有限集,则称<G,∗><G,*>是有限群.反之则为无限群

(2)只含有幺元的群叫平凡群

(3)若∗*运算时可交换的,则称<G,∗><G,*>是交换群或阿贝尔群

#学习 #记录 #离散数学
Post Date
Post Update Date

离散数学:半群,独异点

半群定义,独异点定义

设 SS是非空集合,∗*是SS上的二元运算,如果∗*在SS上满足封闭性 可结合性 ,则称<S,∗><S,*>是半群

独异点定义

设<M,∗><M,*>是个半群,如果∗*运算有幺元,则称<M,∗><M,*>是独异点,也称它为含幺半群

可交换半群

设<M,∗><M,*>是个半群,如果∗*运算是可交换的,则称<M,∗><M,*>是可交换半群

可交换独异点

设<M,∗><M,*>是个独异点,如果∗*运算是可交换的,则称<M,∗><M,*>是**可交换独异点

子半群

设<S,∗><S,*>是个半群,B∈SB\in S,如果∗*在BB上封闭,则称<B,∗><B,*>是<S,∗><S,*>的子半群

子独异点

设<S,∗><S,*>是个独异点,B∈SB\in S,如果∗*在BB上封闭,且幺元e∈Be \in B,则称<B,∗><B,*>是<S,∗><S,*>的子独异点

#学习 #抽象 #离散数学