编译原理知识点1

字符串与字母表的定义

注:文章里的 _ 代表 下标,^ 代表次方 或 标记。

​ 例如:V_N V_T α->^+β

$$ V_N V_T \\ α =>^+β $$

字母表:非空有穷集合,字母表的元素称为 符号,里面包括 汉字、标点符号、数字等。

符号:字母表的元素,语法分析时的 单词 ,词法分析时的 源码字符

符号串:由 字母表 中的符号组成任何 有穷序列 称为符号串。

空符号串:无任何 符号 的符号串或 长度 为零的符号串,记作 ε 。(epsilon,音标/ep'silon/)

字符串集合:当A集合所有元素都是某个 字母表 的的元素,则A集合是该字母表的集合。

字符串相等:x和y 字符串 每个符号依次相等。

字符串长度:当 x=abc x长度就为3 ,则用|x| =3 代表字符串长度。

字符串集合的幂运算:a的0次方等于{ε} ,a的1次方等于{a}。a的n次方等于{aa...N-1} 当N>0。

字符串的闭包运算:A+ 称为A的 正闭包 ,A* 称为 闭包

A+ 集合定义:例如 A={a} ,A+ 等于{a,aa,aaa,aaa,aaaa }。

A*集合定义:{ ε ∪ A+ }。

文法与语言的形式定义

文法是对语言结构的定义描述,即从形式上用于描述和规定语言的结构称为文法或语法。

非终结符:可以被取代的符号,非空有穷集合。(比如变量)

终结符:不可分解的单位,非空有穷集合。(比如常量)

产生式:条件规则 ,非空又穷集合。例如 α -> β

文法G:定义为四元组 G( V_n , V_t , P , S)。其中V_n 为 非终结符, V_t为 终结符, P为 产生式 ,S为 识别符号开始符号。 V 通常表示 V_n和V_t 。

α -> β 推导,相当于 α替换β ,称为 直接推导。也可以称 β 直接归约 α。

如果α -> β 经过多步推导推出 步数n>0,标记为 α ->^+ β 或 α ->n+ β n为步数。 α ->^* β 包括有0步推导。

列子: 大写 字母代表 非终结符 小写字母代表 终结符

$$ S=>A \\ A=>c \\ $$

所以A->c 只需要1步推到 标记为:

$$ α =>^1 β $$

添加新评论

评论列表