Exe1-程序语言的基本知识.ppt

练习: 1. 文法: Z → U0 | V1 U →Z1 | 1 V → Z0 | 0 (1)请写出全部由此文法描述的只含有四个符号的句子. (2)该文法是 Chomsky 几型文法? 1. 文法: Z → U0 | V1 U →Z1 | 1 V → Z0 | 0 请写出全部由此文法描述的只含有四个符号的句子: 0101, 1010, 1001, 0110 . 该文法是 Chomsky 几型文法? 3 型文法 2、给定前缀表示的表达式文法 G : (1) E → -EE (2) E → -E (3) E → a (4) E → b (5) E → c 试问 --a-bc 是否 L(G) 的句子?若是,请给出该句子所有可能的分析树;若不是,请说明理由. 2.1 P26 2.2 文法 G : P → PaP | PbP | cP | Pe | f 证明文法 G 是二义文法. 练习: 1. 文法: S → ( L ) | a L → L , S | S 分析句型: ( L , a , S ) 求：短语、直接短语、句柄、素短语、最左素短语 2. 文法: S → a│^│( T ) T → T , S│S 分析句型: ( T , ( ^ , a ) ) 求：短语、直接短语、句柄、素短语、最左素短语 * * E 可能的分析树(1): - E E - E E c a - E b E 可能的分析树(2): - E E - E - E a b c E E 可能的分析树(3): - E - E E c a - E b E S ( L ) ( a , ( a , a ) ) a a S S , L ( L ) S , L a S 最左推导：S (L) (L,S) (S,S) (a,S) (a,(L)) (a,(L,S)) (a,(S,S)) (a,(a,S)) (a,(a,a)) 最右推导：S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,a)) (L,(S,a)) (L,(a,a)) (S,(a,a)) (a,(a,a)) S b abab S S a b S a S ε ε S b S S a a S b S ε ε ε ε 最左推导：S aSbS abSaSbS abaSbS ababS abab 最左推导：S aSbS abS abaSbS ababS abab ** 通过证明句型 f b f b f 存在两棵分析树. P P b P P b P f f f P P b P P b P f f f 最左推导：P PbP PbPbP fbPbP fbfbP fbfbf 最左推导：P PbP fbP fbPbP fbfbP fbfbf S 句型：( L , a , S ) 短语： ( L , a , S )、 L , a , S、 L , a、a 直接短语：a 句柄：a 素短语：a 最左素短语： a ( L ) L , S L , S a *