Chương trình dịch - 20


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à:


Trạng thái

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!

Xem toàn bộ 224 trang tài liệu này.

Chương trình dịch - 20

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


Stt

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


8

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


Stt

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



22

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.

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 28/06/2022