intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài tập trình biên dịch

Chia sẻ: Le Xuan Phi | Ngày: | Loại File: PDF | Số trang:5

407
lượt xem
60
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các bài tập hữu ích cho môn trình biên dịch. Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài tập trình biên dịch

  1. Chương 2 Bài 1. Cho văn ph m phi ng c nh sau: (1) stmt → id := expr (2) expr → expr + expr | (3) expr ∗ expr | (4) id | (5) num a) Vi t các lu t sinh d n ra câu nh p: a := b + 10 + c*50 b) Xây d ng m t cây phân tích cú pháp cho câu nh p trên ? Bài 2. Cho văn ph m G ch a các lu t sinh sau: S → ( L) a L → L, S | S a) Hãy ch ra các thành ph n c a văn ph m phi ng c nh cho G. b) Vi t văn ph m tương ñương sau khi lo i b ñ quy trái Bài 3. Cho văn ph m phi ng c nh sau: S → id := E E → E + E | E ∗ E | id | num a) Vi t các lu t sinh d n ra câu nh p: t1:= t2 + t3*10 + 60 b) Xây d ng m t cây phân tích cú pháp cho câu nh p trên? Bài 4. Cho văn ph m phi ng c nh sau: S→SS+|SS*|a a) Vi t các lu t sinh d n ra câu nh p: a a + a * b) Xây d ng m t cây phân tích cú pháp cho câu nh p trên? c) Văn ph m này sinh ra ngôn ng gì? Gi i thích câu tr l i. Bài 5. Ngôn ng gì sinh ra t các văn ph m sau? Văn ph m nào là văn ph m mơ h ? a) S → 0 S 1 | 0 1 b) S → + S S | - S S | a c) S → S ( S ) S | ε d) S → a S b S | b S a S | ε e) S → a | S + S | S S | S * | ( S ) Bài 6. Cho các Văn ph m: 1. G1 v i P1: S → SS | aSb | bSa | ab| ba. 2. G2 v i P2: S→ aS | a. 3. G3 v i P3: S → aS | Sb | aSb| c. 4. G4 v i P4: S → SS | b | a. 5. G5 v i P5: S → aA | bB | c. A → Sa B → Sb. Hãy: a. Vi t l i t ng Văn ph m dư i d ng ñ y ñ theo ñ nh nghĩa.
  2. b. Tìm các ngôn ng do các Văn ph m trên sinh ra. Chương 3 Bai 1. Hãy xác ñ nh các tr t v ng có th hình thành các token trong các ño n chương trình sau: a. PASCAL function max (i, j :integer) : integer; { Tr v s nguyên l n hơn trong 2 s i và j } begin i > j then max : = i else max : = j; end; b. C int max (i, j) int i, j; /* Tr v s nguyên l n hơn trong 2 s i và j */ { return i > j ? i : j } Bài 2. Vi t m t chương trình Lex sao chép m t t p tin, thay các chu i kho ng tr ng thành m t kho ng tr ng duy nh t. Bài 3. Vi t m t ñ c t Lex cho các token c a ngôn ng Pascal và dùng trình biên d ch Lex ñ xây d ng m t b phân tích t v ng cho Pascal. Chương 4 Bài 1. Cho văn ph m G ch a các lu t sinh sau: S → ( L) | a L→L,S|S a) Hãy ch ra các thành ph n c a văn ph m phi ng c nh cho G. b) Vi t văn ph m tương ñương sau khi lo i b ñ quy trái . c) Xây d ng b phân tích cú pháp d ñoán cho văn ph m. d) Hãy dùng b phân tích cú pháp ñã ñư c xây d ng ñ v cây phân tích cú pháp cho các câu nh p sau: i) (a, a) ii) (a, (a, a)) iii) (a, (a, a), (a, a))) Bài 2. Cho văn ph m G ch a các lu t sinh sau: S → aSbS | bSaS | ε a) Ch ng minh văn ph m này là mơ h b ng cách xây d ng 2 chu i d n xu t trái khác nhau cho cùng câu nh p abab. b) Xây d ng các chu i d n xu t ph i tương ng cho câu nh p abab. c) V các cây phân tích cú pháp tương ng.
  3. Bài 3. Cho văn ph m G ch a các lu t sinh sau: bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor → not bfactor | (bexpr) | true | false a) Hãy xây d ng b phân tích cú pháp d ñoán cho văn ph m G. b) Xây d ng cây phân tích cú pháp cho câu : not ( true and false ) c) Ch ng minh r ng văn ph m này sinh ra toàn b các bi u th c boole. d) Văn ph m G có là văn ph m mơ h không ? T i sao ? Bài 4. Cho văn ph m sau: G ({expr, term, factor}, {or, and, not, true, false}, P, expr) P ={ expr → expr or term | term term → term and factor | factor factor → not factor | (expr) | true | false } a. Hãy v sơ ñ cú pháp cho các ký hi u không k t thúc. b. Vi t chương trình cho sơ ñ cú pháp t ng quát expr c a câu a. Bài 5. Cho văn ph m G = ({S0,A,B}, {id, true, false, if, then, else,=, ; }, P, S0, v i t p lu t sinh P như sau: S0→ S S → if B then S | if B then S else S | A; B → true | false A → id | A = id a. Hãy v sơ ñ cú pháp cho các ký hi u không k t thúc. b. Vi t chương trình cho sơ ñ cú pháp A. Bài 6. Cho văn ph m G = ({S,A,B,C}, {a, b, c}, P, S) v i t p lu t sinh P như sau: S → ABC A → bA|B|a B → Ba|bC|ba C → B|cba|ca|c Hãy tính FIRST, FOLLOW cho t t c các ký hi u không k t thúc c a văn ph m. Bài 7. Cho văn ph m G = ({S,A,B,C}, {a, b, c}, P, S) v i t p lu t sinh P như sau: S → ABC A → bA|B|a B → Ba|bC|ba C → B|cba|ca|c Hãy tính FIRST, FOLLOW cho t t c các ký hi u không k t thúc c a văn ph m
  4. Chương 5 Bài 1. Xây d ng m t cây phân tích cú pháp chú thích cho bi u th c s h c sau: (4 * 7+ 1) * 2 Bài 2. Xây d ng m t cây phân tích cú pháp và cây cú pháp cho bi u th c ((a) + (b)) theo: a) Ð nh nghĩa tr c ti p cú pháp cho bi u th c s h c. b) Lư c ñ d ch cho bi u th c s h c. Bài 3. Xây d ng m t DAG cho các bi u th c sau ñây: a) a + a + ( a+ a + a + ( a+ a+ a+ a)) b) x *( 3 *x + x * x) Bài 4. Cho văn ph m sinh ra các dòng text như sau: S→L L→LB|B B → B sub F | F F → { L } | text a) Xây d ng m t ñ nh nghĩa tr c ti p cú pháp cho văn ph m. b) Chuy n ñ nh nghĩa tr c ti p cú pháp trên thành lư c ñ d ch. c) Lo i b ñ quy trái trong lư c ñ d ch v a xây d ng. Chương 7 Bài 1. D ch bi u th c : a * - ( b + c) thành các d ng: a) Cây cú pháp. b) Ký pháp h u t . c) Mã l nh máy 3 - ñ a ch . Bài 2. Trình bày c u trúc lưu tr bi u th c - ( a + b) * ( c + d ) + ( a + b + c) các d ng: a) B t . b) B tam. Bài 3. Sinh mã trung gian ( d ng mã máy 3 - ñ a ch ) cho các bi u th c C ñơn gi n sau: a) x = 1 b) x = y c) x = x + 1 d) x = a + b * c e) x = a / ( b + c) - d * ( e + f ) Bài 4. Sinh mã trung gian ( d ng mã máy 3 - ñ a ch ) cho các bi u th c C sau: a) x = a [i] + 11 b) a [i] = b [ c[j] ]
  5. c) a [i][j] = b [i][k] * c [k][j] d) a[i] = a[i] + b[j] e) a[i] + = b[j] Bài 5. D ch l nh gán sau thành mã máy 3 - ñ a ch : A [ i,j ] := B [ i,j ] + C [A[ k,l]] + D [ i + j ]
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2