Hãy sử dụng giải thuật phân tích cú pháp đẩy – thu để phân tích mỗi xâu vào w; sau đó xây dựng cây phân tích cú pháp của nó nếu có:
1) w = id - (id + id).
2) w = (id + id) / id.
3) w = (id + id)- (id.
4) w = id + * (id - id) / id.
5) w = (id + id) / (id + id).
6) w = id * id - id) + id.
7) w = id * (id + id)/(id - id).
3.46. Cho văn phạm có các luật sinh sau:
1. E E+T ;
2. E T ; 3.T T*F ; 4.T F ;
5. F (E) ;
6. F id.
Với bảng phân tích cú pháp là:
Action | Goto | ||||||||
id | + | * | ( | ) | $ | E | T | F | |
0 | s5 | s4 | 1 | 2 | 3 | ||||
1 | s6 | acc | |||||||
2 | r2 | s7 | r2 | r2 | |||||
3 | r4 | r4 | r4 | r4 | |||||
4 | s5 | s4 | 8 | 2 | 3 | ||||
5 | r6 | r6 | r6 | r6 | |||||
6 | s5 | s4 | 9 | 3 | |||||
7 | s5 | s4 | 10 | ||||||
8 | s6 | s11 | |||||||
9 | r1 | s7 | r1 | r1 | |||||
10 | r3 | r3 | r3 | r3 | |||||
11 | r5 | r5 | r5 | r5 |
Có thể bạn quan tâm!
-
A. Cây Phân Tích Cú Pháp Của Xâu Id * Id + Id Được Xây Dựng Từ Dưới Lên Theo Phương Pháp Đẩy-Thu -
Chương trình dịch - 18 -
Chương trình dịch - 19 -
Chương trình dịch - 21 -
Chương trình dịch - 22 -
Chương trình dịch - 23
Xem toàn bộ 224 trang tài liệu này.
Bảng BT 3.464.6 Bảng phân tích cú pháp SLR
Hãy sử dụng giải thuật phân tích cú pháp LR để phân tích xâu vào:
1) w = id * (id + id).
2) w = id + id + id).
3) w = id + * id + id.
4) w = id + (id + id).
5) w = (id + (id + id))* id.
6) w = (id + id) * (id + id).
7) w = id * ((id + id)* id).
3.47. Cho văn phạm sinh biểu thức toán học với các quy tắc sinh: E → E * T | T;
T → T + F | F ;
F → F / G | G ; G → G - B | B;
B → (E) | id .
1) Xây dựng họ tập hợp mục LR(0) của văn phạm.
2) Xây dựng các hàm action và hàm goto cho bảng phân tích cú pháp SLR của văn phạm.
3) Xây dựng bảng phân tích cú pháp SLR cho văn phạm.
4) Sử dụng giải thuật phân tích cú pháp để phân tích xâu vào:
1) w = id - (id + id).
2) w = (id + id) / id.
3) w = (id + id) - (id.
4) w = id + * (id - id) / id.
5) w = (id + id) / (id + id).
6) w = id * id - id) + id.
7) w = id * (id + id)/(id - id).
LỜI GIẢI TÓM TẮT HOẶC HƯỚNG DẪN
CHƯƠNG 1
1.9. Lời giải tóm tắt
1. digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Thì: + digit là thẻ từ (token);
+ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern) của thẻ từ digit;
+ Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một từ vị (lexeme) của thẻ từ digit.
2. digits digit(digit)*
Thì: + digits là thẻ từ (token);
+ Biểu thức chính quy digit(digit)* là mẫu từ vựng (pattern) của thẻ từ digits;
+ Mỗi số: 0, 1, 20, 135, ... là một từ vị (lexeme) của thẻ từ digits.
3. optional_fraction . digits | ε
Thì: + optional_fraction là thẻ từ (token);
+ Biểu thức chính quy . digits | ε là mẫu từ vựng (pattern) của thẻ từ optional_fraction;
+ Mỗi: ε, .0, .5, .21, .135, ... là một từ vị (lexeme) của thẻ từ optional_fraction.
4. optional_exponent ( E ( + | - | ε ) digits) | ε Thì: + optional_exponent là thẻ từ (token);
+ Biểu thức chính quy ( E ( + | - | ε ) digits) | ε là mẫu từ vựng (pattern) của thẻ từ optional_exponent;
+ Mỗi: ε, E-1, E5, E+2, E135, ... là một từ vị (lexeme) của thẻ từ optional_exponent.
5. nums digits optional_fraction optional_exponent Thì: + nums là thẻ từ (token);
+ Biểu thức chính quy: digits optional_fraction optional_exponent là mẫu từ vựng (pattern) của thẻ từ num;
+ Mỗi: 1, 126, 572E-1, 329.22 E5, 143.0 E+2, ... là một từ vị (lexeme) của thẻ từ nums.
1.10. Lời giải tóm tắt
a) Với ngôn ngữ lập trình bậc cao Pascal
1. Kiểu dữ liệu
- Số nguyên (integer)
digit 0 | 1 |...| 9 ; sign + | - | ε ;
*
digits (sign)(digit)(digit)
- Số nguyên ngắn (sortint)
- Số nguyên dài (longint)
- Số thực (real)
+ Số thực dấu phảy tĩnh optional_fraction . digits | ε ;
number (sign)(digits)(optional_fraction)
+ Số thực dấu phảy động
optional_exponent ( E ( + | - | ε ) digits) | ε;
nums digits optional_fraction optional_exponent.
- Ký tự (Char) – bảng chữ cái
Char A | B | ...| Z | a | b |...| z | 0 | 1|...| 9| ( | ) | [ | ] | { | }| ?| < | -| +| ...
- Xâu ký tự (String)
*
String (char)(char)
- logic (boolean)
Boolean true | false
...
2. Phép toán quan hệ (Relop) relop < | <= | > | >= | <>
3. Phép toán số học (operator)
Operator +-*/**
4. Phép gán (Assign) Assign :=
5. Tên (Identifer)
letter A | B | ...| Z | a | b |...| z ; digit 0 | 1 | ...| 9 ;
id (letter| _ ) (letter | digit | _ )*
6. Tên chuẩn (standard identifer)
Integer Integer; Shortint Shortint; longint longint; real real;
Char Char; String String; Boolean Boolean; pi 3.141...;
Ngoài ra còn nhiều tên chuẩn khác như: sqr, sqrt, copy, val, max, min, ...
7. Từ khóa (Keyword)
If if;
then then; else else; while while; do do;
to to; for for;
repeat repeat; until until; program program; label label;
const const; var var;
function function; procedure procedure; begin begin
end end
8. Các dấu (Signs) ,
- semi ;
- comma ,
- Dot .
- twodot :
...
9. Dấu cách, dấu tab, dấu xuống dòng delim blank | tab | newline ;
+
ws delim .
10. othersign (, ), …
…
b) Với ngôn ngữ lập trình bậc cao C: Tương tự
CHƯƠNG 2
2.10. Lời giải tóm tắt
Token | Lexeme | |
1 | function | function |
2 | begin | begin |
3 | if | if |
4 | then | then |
5 | else | else |
6 | end | end |
7 | id | max2, i , j |
integer | Integer | |
9 | Assign | : = |
10 | twocham | : |
11 | relop | > |
12 | semi | ; |
Bảng BT 2.10.
2.11. Lời giải tóm tắt
Token | Lexeme | |
1 | PROGRAM | PROGRAM |
2 | VAR | VAR |
3 | FUNCTION | FUNCTION |
4 | Begin | Begin |
5 | End | End |
6 | PROCEDURE | PROCEDURE |
7 | REPEAT | REPEAT |
8 | UNTIL | UNTIL |
9 | If | If |
10 | Then | Then |
11 | Id | GPTB2, a, b, c, x1, x2, Delta, Ptb2, r |
12 | Semi | ; |
13 | Comma | , |
14 | Twocham | : |
15 | Real | real |
16 | Assign | := |
17 | Sqr | Sqr |
18 | Sqrt | Sqrt |
19 | Write | Write |
20 | Writeln | Writeln |
21 | readln | readln |
Operator | -, +, *, /, | |
23 | othersign | (, ) |
24 | litral | „a=‟, „b=‟, „c=‟, „PT vo nghiem‟, „PT co nghiem kep x1 = x2 =‟, „x2 =‟, „PT co 2 nghiem: x1=‟ |
25 | relop | <>, <, >, =, |
26 | digits | 0, 1, 2 |
27 | dot | . |
Bảng BT 2.11.
2.12. Lời giải tóm tắt
a) Hãy biểu diễn mỗi thẻ từ bằng định nghĩa chính quy và chỉ ra thẻ từ, mẫu từ vựng, trị từ vựng của mỗi thẻ từ.
1) digit 0 | 1 |...| 9 ; digits (digit)(digit)*
2) digit 0 | 1 |...| 9 ; sign + | - | ε ;
digits (sign)(digit)(digit)*
3) digit 0 | 1 |...| 9 ; sign + | - | ε ;
digits (sign)(digit)(digit)*
optional_fraction . digits | ε ;
number (sign)(digits)(optional_fraction) .
4) digit 0 | 1 |...| 9 ; sign + | - | ε ;
digits (sign)(digit)(digit)*
optional_fraction . digits | ε ; optional_exponent ( E ( + | - | ε ) digits) | ε;
nums digits optional_fraction optional_exponent.