Giáo trình Xây dựng chương trình dịch - Chương II: Một trình biên dịch đơn giản

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương II: Một trình biên dịch đơn giản

1. Xem như một quy tắc tổng quát, phần lớn các phương pháp phân tích cú pháp đều xử lý input của chúng từ trái sang phải, trong lược đồ dịch đơn giản (lược đồ dịch dẫn xuất từ một định nghĩa trực tiếp cú pháp đơn giản), các hành vi ngữ nghĩa cũng được thực hiện từ trái sang phải. Vì thế, để cài đặt một lược đồ dịch đơn giản, chúng ta có thể thực hiện các hành vi ngữ nghĩa trong lúc phân tích cú pháp mà không nhất thiết phải xây dựng cây phân tích cú pháp. III. PHÂN TÍCH CÚ PHÁP (PARSING) Phân tích cú pháp là quá trình xác định xem liệu một chuỗi ký hiệu kết thúc (token) có thể được sinh ra từ một văn phạm hay không ? Khi nói về vấn đề này, chúng ta xem như đang xây dựng một cây phân tích cú pháp, mặc dù một trình biên dịch có thể không xây dựng một cây như thế. Tuy nhiên, quá trình phân tích cú pháp (parse) phải có khả năng xây dựng nó, nếu không thì việc phiên dịch sẽ không bảo đảm được tính đúng đắn. Phần lớn các phương pháp phân tích cú pháp đều rơi vào một trong 2 lớp: phương pháp phân tích từ trên xuống và phương pháp phân tích từ dưới lên. Những thuật ngữ này muốn đề cập đến thứ tự xây dựng các nút trong cây phân tích cú pháp. Trong phương pháp đầu, quá trình xây dựng bắt đầu từ gốc tiến hành hướng xuống các nút lá, còn trong phương pháp sau thì thực hiện từ các nút lá hướng về gốc. Phương pháp phân tích từ trên xuống thông dụng hơn nhờ vào tính hiệu quả của nó khi xây dựng theo lối thủ công. Ngược lại, phương pháp phân tích từ dưới lên lại có thể xử lý được một lớp văn phạm và lược đồ dịch phong phú hơn. Vì vậy, đa số các công cụ phần mềm giúp xây dựng thể phân tích cú pháp một cách trực tiếp từ văn phạm đều có xu hướng sử dụng phương pháp từ dưới lên. 1. Phân tích cú pháp từ trên xuống (Top - Down Parsing) Xét văn phạm sinh ra một tập con các kiểu dữ liệu của Pascal type → simple | ↑ id | array [simple] of type simple → integer | char | num num Phân tích trên xuống bắt đầu bởi nút gốc, nhãn là ký hiệu chưa kết thúc bắt đầu và lặp lại việc thực hiện hai bước sau đây: 1. Tại nút n, nhãn là ký hiệu chưa kết thúc A, chọn một trong những luật sinh của A và xây dựng các con của n cho các ký hiệu trong vế phải của luật sinh. 2. Tìm nút kế tiếp mà tại đó một cây con sẽ được xây dựng. Ðối với một số văn phạm, các bước trên được cài đặt bằng một phép quét (scan) dòng nhập từ trái qua phải. Ví dụ 2.10: Với các luật sinh của văn phạm trên, ta xây dựng cây cú pháp cho dòng nhập: array [num num] of integer Mở đầu ta xây dựng nút gốc với nhãn type. Ðể xây dựng các nút con của type ta chọn luật sinh type → array [simple] of type. Các ký hiệu nằm bên phải của luật sinh này là array, [, simple, ], of, type do đó nút gốc type có 6 con có nhãn tương ứng (áp dụng bước 1) Trong các nút con của type, từ trái qua thì nút con có nhãn simple (một ký hiệu chưa kết thúc) do đó có thể xây dựng một cây con tại nút simple (bước 2) 19
2. match (‘↑‘); match(id); end else if lookahead = array then begin match(array); match(‘[‘); simple; match(‘]’); match(of); type end else error; end; procedure simple; begin if lookahead = integer then match(integer) else if lookahead = char then match(char) else if lookahead = num then begin match(num); match(dotdot); match(num); end else error end; Hình 2.9 - Ðoạn mã giả minh họa phương pháp phân tích dự đoán Phân tích cú pháp bắt đầu bằng lời gọi tới thủ tục cho ký hiệu bắt đầu type. Với dòng nhập array [num num] of integer thì đầu đọc lookahead bắt đầu sẽ đọc token array. Thủ tục type sau đó sẽ thực hiện chuỗi lệnh: match(array); match(‘[‘); simple; match(‘]’); match(of); type. Sau khi đã đọc được array và [ thì ký hiệu hiện tại là num. Tại điểm này thì thủ tục simple và các lệnh match(num); match(dotdot); match(num) được thực hiện. Xét luật sinh type → simple. Luật sinh này có thể được dùng khi ký hiệu dò tìm sinh ra bởi simple, chẳng hạn ký hiệu dò tìm là integer mặc dù trong văn phạm không có luật sinh type → integer, nhưng có luật sinh simple → integer, do đó luật sinh type → simple được dùng bằng cách trong type gọi simple. Phân tích dự đoán dựa vào thông tin về các ký hiệu đầu sinh ra bởi vế phải của một luật sinh. Nói chính xác hơn, giả sử ta có luật sinh A → γ , ta định nghĩa tập hợp : FIRST(γ) = { token | xuất hiện như các ký hiệu đầu của một hoặc nhiều chuỗi sinh ra bởi γ }. Nếu γ là ε hoặc có thể sinh ra ε thì ε ∈ FIRST(γ). Ví dụ 2.12: Xét văn phạm như trên, ta dễ dàng xác định: FIRST( simple) = { integer, char, num } 21
3. IV. MỘT CHƯƠNG TRÌNH DỊCH BIỂU THỨC ÐƠN GIẢN Sử dụng các kỹ thuật nêu trên, chúng ta xây dựng một bộ dịch trực tiếp cú pháp mà nó dịch một biểu thức số học đơn giản từ trung tố sang hậu tố. Ta bắt đầu với các biểu thức là các chữ số viết cách nhau bởi + hoặc -. Xét lược đồ dịch cho dạng biểu thức này : expr → expr + term { print (‘+’) } expr → expr - term { print (‘-’) } expr → term term → 0 { print (‘0’) } term → 9 { print (‘9’) } Hình 2.10 - Ðặc tả lược đồ dịch khởi đầu Văn phạm nền tảng cho lược đồ dịch trên có chứa luật sinh đệ qui trái, bộ phân tích cú pháp dự đoán không xử lý được văn phạm dạng này, cho nên ta cần loại bỏ đệ quy trái bằng cách đưa vào một ký hiệu chưa kết thúc mới rest để được văn phạm thích hợp như sau: expr → term rest rest → + term { print(‘+’) } rest | - term {print(‘-’) rest | ε term → 0 { print(‘0’) } term → 1 { print(‘1’) } term → 9 { print(‘9’) } Hình sau đây mô tả quá trình dịch biểu thức 9 - 5 + 2 dựa vào lược đồ dịch trên: expr term rest 9 { print(‘9’) } - term { print(‘-’) } rest + term { print(+’) } rest 5 { print(‘5’) } 2 { print(‘2’) } ε Hình 2.11 - Dịch 9 - 5+2 thành 9 5- 2+ Bây giờ ta cài đặt chương trình dịch bằng C theo đặc tả như trên. Phần chính của chương trình này là các đoạn mã C cho các hàm expr, term và rest. // Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr expr( ) 23
4. } else ; } Nhờ sự thay thế này, hai hàm rest và expr có thể được tích hợp lại thành một. Mặt khác, trong C, một câu lệnh stmt có thể được thực hiện lặp đi lặp lại bằng cách viết : while (1) stmt với 1 là điều kiện hằng đúng. Chúng ta cũng có thể thóat khỏi vòng lặp dễ dàng bằng lệnh break. Ðoạn chương trình có thể được viết lại như sau : expr ( ) { term ( ) while (1) if (lookahead = = ‘+’ ) { match(‘+’) ; term( ) ; putchar (‘+ ‘) ; } else if (lookahead = = ‘-’) { match(‘-’) ; term( ) ; putchar (‘-’) ; } else break; } Chương trình C dịch biểu thức trung tố sang hậu tố Chương trình nguồn C hoàn chỉnh cho chương trình dịch có mã như sau : # include /* nạp tập tin chứa isdigit vào*/ int lookahead; main ( ) { lookahead = getchar( ); expr( ) ; putchar(‘ \n‘); /* thêm vào ký tự xuống hàng */ } expr( ) { term( ); while(1) 25
5. hoặc các dòng chú thích (comment) phải bị bỏ qua. Khi bộ phân tích từ vựng đã bỏ qua các khoảng trắng này thì bộ phân tích cú pháp không bao giờ xem xét đến chúng nữa. Chọn lựa cách sửa đổi văn phạm để đưa cả khoảng trắng vào trong cú pháp thì hầu như rất khó cài đặt. 2. Xử lý các hằng Bất cứ khi nào một ký tự số xuất hiện trong biểu thức thì nó được xem như là một hằng số. Bởi vì một hằng số nguyên là một dãy các chữ số nên nó có thể được cho bởi luật sinh văn phạm hoặc tạo ra một token cho hằng số đó. Bộ phân tích từ vựng có nhiệm vụ ghép các chữ số để được một số và sử dụng nó như một đơn vị trong suốt quá trình dịch. Ðặt num là một token biểu diễn cho một số nguyên. Khi một chuỗi các chữ số xuất hiện trong dòng nhập thì bộ phân tích từ vựng sẽ gửi num cho bộ phân tích cú pháp. Giá trị của số nguyên được chuyển cho bộ phân tích cú pháp như là một thuộc tính của token num. Về mặt logic, bộ phân tích từ vựng sẽ chuyển cả token và các thuộc tính cho bộ phân tích cú pháp. Nếu ta viết một token và thuộc tính thành một bộ nằm giữa thì dòng nhập 31 + 28 + 59 sẽ được chuyển thành một dãy các bộ : , , , , . Bộ cho thấy thuộc tính của + không có vai trò gì trong khi phân tích cú pháp nhưng nó cần thiết dùng đến trong quá trình dịch. 3. Nhận dạng các danh biểu và từ khóa Ngôn ngữ dùng các danh biểu (identifier) như là tên biến, mảng, hàm và văn phạm xử lý các danh biểu này như là một token. Người ta dùng token id cho các danh biểu khác nhau do đó nếu ta có dòng nhập count = count + increment; thì bộ phân tích từ vựng sẽ chuyển cho bộ phân tích cú pháp chuỗi token: id = id + id (cần phân biệt token và trị từ vựng lexeme của nó: token id nhưng trị từ vựng (lexeme) có thể là count hoặc increment). Khi một lexeme thể hiện cho một danh biểu được tìm thấy trong dòng nhập cần phải có một cơ chế để xác định xem lexeme này đã được thấy trước đó chưa? Công việc này được thực hiện nhờ sự lưu trữ trợ giúp của bảng ký hiệu (symbol table) đã nêu ở chương trước. Trị từ vựng được lưu trong bảng ký hiệu và một con trỏ chỉ đến mục ghi trong bảng trở thành một thuộc tính của token id. Nhiều ngôn ngữ cũng sử dụng các chuỗi ký tự cố định như begin, end, if, để xác định một số kết cấu. Các chuỗi ký tự này được gọi là từ khóa (keyword). Các từ khóa cũng thỏa mãn qui luật hình thành danh biểu, do vậy cần qui ước rằng một chuỗi ký tự được xác định là một danh biểu khi nó không phải là từ khóa. Một vấn đề nữa cần quan tâm là vấn đề tách ra một token trong trường hợp một ký tự có thể xuất hiện trong trị từ vựng của nhiều token. Ví dụ một số các token là các toán tử quan hệ trong Pascal như : . 4. Giao diện của bộ phân tích từ vựng Bộ phân tích từ vựng được đặt xen giữa dòng nhập và bộ phân tích cú pháp nên giao diện với hai bộ này như sau: 27
6. Dùng getchar() đọc Trả token cho input Bộ phân tích bên gọi từ vựng Đẩy ký tự trở về bằng lexan ( ) ungetc (c, stdin) Đặt giá trị thuộc tính vào biến toàn cục tokenval Hình 2.13 - Cài đặt giao diện của bộ phân tích từ vựng Nếu ngôn ngữ cài đặt không cho phép trả về các cấu trúc dữ liệu từ các hàm thì token và các thuộc tính của nó phải được truyền riêng rẽ. Hàm lexan trả về một số nguyên mã hóa cho một token. Token cho một ký tự có thể là một số nguyên quy ước được dùng để mã hóa cho ký tự đó. Một token như num có thể được mã hóa bằng một số nguyên lớn hơn mọi số nguyên được dùng để mã hóa cho các ký tự, chẳng hạn là 256. Ðể dễ dàng thay đổi cách mã hóa, chúng ta dùng một hằng tượng trưng NUM thay cho số nguyên mã hóa của num. Hàm lexan trả về NUM khi một dãy chữ số được tìm thấy trong input. Biến toàn cục tokenval được đặt là giá trị của chuỗi số này. Cài đặt của hàm lexan như sau : # include # include int lineno = 1; int tokenval = NONE; int lexan ( ) { int t; while(1) { t = getchar( ); if ( t = = ‘ ‘ || t = = ‘\t‘) ; /* loại bỏ blank và tab */ else if (t = = ‘\n’) lineno = lineno + 1; else if ( isdigit (t) ) { tokenval = t - ‘0’; t = getchar( ); while ( isdigit (t) ) { tokenval = tokenval * 10 + t - ‘0’; t = getchar( ); 29
7. bảng ký hiệu như là một danh sách có thứ tự của các từ khóa. Trong quá trình phân tích từ vựng, khi một trị từ vựng được xác định thì ta phải tìm (nhị phân) trong danh sách các từ khóa xem có trị từ vựng này không. Nếu có, thì trị từ vựng đó là một từ khóa, ngược lại, đó là một danh biểu và sẽ được đưa vào bảng ký hiệu. 3. Cài đặt bảng ký hiệu Cấu trúc dữ liệu cụ thể dùng cài đặt cho một bảng ký hiệu được trình bày trong hình dưới đây. Chúng ta không muốn dùng một lượng không gian nhớ nhất định để lưu các trị từ vựng tạo ra một danh biểu bởi vì một lượng không gian cố định có thể không đủ lớn để lưu các danh biểu rất dài và cũng rất lãng phí khi gặp một danh biểu ngắn. Thông thường, một bảng ký hiệu gồm hai mảng : 1. Mảng lexemes (trị từ vựng) dùng để lưu trữ các chuỗi ký tự tạo ra một danh biểu, các chuỗi này ngăn cách nhau bởi các ký tự EOS (end - of - string). 2. Mảng symtable với mỗi phần tử là một mẩu tin (record) bao gồm hai trường, trường con trỏ lexptr trỏ tới đầu trị từ vựng và trường token. Cũng có thể dùng thêm các trường khác để lưu trữ giá trị các thuộc tính. Mục ghi thứ zero trong mảng symtable phải được để trống bởi vì giá trị trả về của hàm lookup trong trường hợp không tìm thấy ô tương ứng cho chuỗi ký hiệu. Symtable Lexptr Token Attributes 0 div 1 mod 2 id 3 id 4 d i v EOS m o d EOS c o u n t EOS i EOS Lexeme Hình 2.14 - Bảng ký hiệu và mảng để lưu các chuỗi Trong hình trên, ô thứ nhất và thứ hai trong bảng ký hiệu dành cho các từ khóa div và mod. Ô thứ ba và thứ tư dành cho các danh biểu count và i. Ðoạn mã (ngôn ngữ giả) cho bộ phân tích từ vựng được dùng để xử lý các danh biểu như sau. Nó xử lý khoảng trắng và hằng số nguyên cũng giống như thủ tục đã nói ở phần trước. Khi bộ phân tích từ vựng đọc vào một chữ cái, nó bắt đầu lưu các chữ cái và chữ số vào trong vùng đệm lexbuf. Chuỗi được tập hợp trong lexbuf sau đó được tìm trong mảng symtable của bảng ký hiệu bằng cách dùng hàm lookup. Bởi vì bảng ký hiệu đã được khởi tạo với 2 ô cho div và mod (hình 2.14) nên nó sẽ tìm thấy 31
8. end; VII. MÁY ẢO KIỂU STACK Ta đã biết rằng kết quả của giai đoạn phân tích là một biểu diễn trung gian của chương trình nguồn mà giai đoạn tổng hợp sử dụng nó để phát sinh mã đích. Một dạng phổ biến của biểu diễn trung gian là mã của một máy ảo kiểu Stack (abstact stack machine - ASM). Trong phần này, chúng ta sẽ trình bày khái quát về một máy ảo kiểu Stack và chỉ ra cách sinh mã chương trình cho nó. Máy ảo này bao gồm 3 thành phần: 1. Vùng nhớ chỉ thị (instructions): là nơi chứa các chỉ thị. Các chỉ thị này rất hạn chế và được chia thành 3 nhóm chính: nhóm chỉ thị số học trên số nguyên, nhóm chỉ thị thao tác trên Stack và nhóm chỉ thị điều khiển trình tự. 2. Vùng Stack: là nơi thực hiện các chỉ thị trên các phép toán số học. 3. Vùng nhớ dữ liệu (data): là nơi lưu trữ riêng các dữ liệu. Hình sau đây minh họa cho nguyên tắc thực hiện của dạng máy này, con trỏ pc (program counter) chỉ ra chỉ thị đang chờ để thực hiện tiếp theo. Các giá trị dùng trong quá trình tính toán được nạp vào đỉnh Stack. Sau khi tính toán xong, kết quả được lưu tại đỉnh Stack. INSTRUCTIONS STACK DATA 1 push 5 16 0 1 2 rvalue 2 11 2 7 3 + 3 1 top 7 4 rvalue 3 4 5 * pc 6 Hình 2.15 - Minh họa hình ảnh một máy ảo kiểu Stack Ví dụ 2.15: Biểu thức (5 + b) * c với b = 11, c = 7 sẽ được thực hiện trên Stack dưới dạng biểu thức hậu tố 5 b + c *. 1. Các chỉ thị số học Máy ảo phải cài đặt mỗi toán tử bằng một ngôn ngữ trung gian Khi gặp các chỉ thị số học đơn giản, máy sẽ thực hiện phép toán tương ứng với hai giá trị trên đỉnh Stack, kết quả cũng được lưu vào đỉnh STACK. Một phép toán phức tạp hơn có thể cần phải được cài đặt như một loạt chỉ thị của máy. Mã chương trình máy ảo cho một biểu thức số học sẽ mô phỏng hành động ước lượng dạng hậu tố cho biểu thức đó bằng cách sử dụng Stack. Việc ước lượng được tiến hành bằng cách xử lý chuỗi hậu tố từ trái sang phải, đẩy mỗi toán hạng vào Stack khi gặp nó. Với một toán tử k - ngôi, đối số cận trái của nó nằm ở (k -1) vị trí bên dưới đỉnh Stack và đối số cận phải nằm tại đỉnh. Hành động ước lượng áp dụng toán tử cho k giá trị trên đỉnh của Stack, lấy toán hạng ra và đặt kết quả trở lại vào Stack. 33
9. div R-value d push 153 + R- value m := * 5. Các chỉ thị điều khiển trình tự Máy ảo kiểu Stack thực hiện các chỉ thị theo đúng thứ tự liệt kê trừ khi được yêu cầu thực hiện khác đi bằng các câu lệnh nhảy có điều kiện hoặc không điều kiện. Có một số các tùy chọn dùng để mô tả các đích nhảy : 1. Toán hạng làm chỉ thị cho biết vị trí đích. 2. Toán hạng làm chỉ thị mô tả khoảng cách tương đối cần nhảy theo chiều tới hoặc lui. 3. Ðích nhảy đến được mô tả bằng các ký hiệu tượng trưng gọi là các nhãn. Một số chỉ thị điều khiển trình tự cho máy là : lable l : Gán đích của các lệnh nhảy đến là l, không có tác dụng khác. goto l : Chỉ thị tiếp theo được lấy từ câu lệnh có lable l . gofalse l : Lấy giá trị trên đỉnh Stack ra, nếu giá trị là 0 thì nhảy đến l, ngược lại, thực hiện lệnh kế tiếp. gotrue l : Lấy giá trị trên đỉnh Stack ra, nếu giá trị khác 0 thì nhảy đến l, ngược lại, thực hiện lệnh kế tiếp. halt : Ngưng thực hiện chương trình. 6. Dịch các câu lệnh Sơ đồ phác thảo đoạn mã máy ảo cho một số lệnh cấu trúc được chỉ ra trong hình sau: IF expr THEN stmt WHILE expr DO stmt Code for expr Label test Gofalse out Code for expr Code for stmt 1 Gofalse out Lable out Code for stmt 1 Goto test Lable out Hình 2.16 - Sơ đồ đoạn mã cho một số lệnh cấu trúc Xét sơ đồ đoạn mã cho câu lệnh If . Giả sử rằng newlable là một thủ tục trả về một 35
10. VIII. KẾT NỐI CÁC KỸ THUẬT Trong các phần trên, chúng ta đã trình bày một số kỹ thuật phiên dịch trực tiếp cú pháp để xây dựng kỳ đầu của trình biên dịch. Phần này sẽ thực hiện việc kết nối chúng lại bằng cách giới thiệu một chương trình C có chức năng dịch trung tố - hậu tố cho một ngôn ngữ gồm dãy các biểu thức kết thúc bằng các dấu chấm phẩy. Các biểu thức gồm có các số, danh biểu, các toán tử +, -, *, /, div và mod. Output cho chương trình là dạng biểu diễn hậu tố cho mỗi biểu thức. 1. Mô tả chương trình dịch Chương trình dịch được thiết kế bằng cách dùng lược đồ dịch trực tiếp cú pháp có dạng như sau : start → list eof list → expr ; list | ε expr → expr + term { print (‘+ ’) } | expr - term { print (‘- ’) } | term term → term * factor { print (‘* ’) } | term / factor { print (‘/ ’) } | term div factor { print (‘DIV’) } | term mod factor { print (‘MOD’) } | factor factor → ( expr ) | id { print (id.lexeme) } | num { print (num.value) } Trong đó, token id biểu diễn một dãy không rỗng gồm các chữ cái và ký số bắt đầu bằng một chữ cái, num là dãy ký số, eof là ký tự cuối tập tin (end - of - file). Các token được phân cách bởi một dãy ký tự blank, tab và newline - gọi chung là các khoảng trắng (white space). Thuộc tính lexeme của token id là chuỗi ký tự tạo ra token dó, thuộc tính value của token num chứa số nguyên được biểu diễn bởi num. Ðoạn mã cho chương trình dịch bao gồm 7 thủ tục, mỗi thủ tục được lưu trong một tập tin riêng. Ðiểm bắt đầu thực thi chương trình nằm trong thủ tục chính main.c gồm có một lời gọi đến init( ) để khởi gán, theo sau là một lời gọi đến parse( ) để dịch. Các thủ tục còn lại được mô tả tổng quan như hình sau: 37
11. list → expr ; list | ε expr → term R1 R1 → + term { print (‘ + ’) } R1 | - term { print (‘ - ’) } R1 | ε term → factor R2 R2 → * factor { print (‘ * ’) } R2 | / factor { print (‘ / ’) } R2 | DIV factor { print (‘DIV’) } R2 | MOD factor { print (‘MOD’) }R2 | ε factor → ( expr ) | id { print (id.lexeme) } | num { print (num.value) } Sau đó, chúng ta xây dựng các hàm cho các ký hiệu chưa kết thúc expr, term và factor. Hàm parse( ) cài đặt ký hiệu bắt đầu start của văn phạm, nó gọi lexan mỗi khi cần một token mới. Bộ phân tích cú pháp ở giai đoạn này sử dụng hàm emit để sinh ra kết quả và hàm error để ghi nhận một lỗi cú pháp. Thủ tục kết xuất emitter.c Thủ tục này chỉ có một hàm emit (t, tval) sinh ra kết quả cho token t với giá trị thuộc tính tval. Thủ tục quản lý bảng ký hiệu symbol.c và khởi tạo init.c Thủ tục symbol.c cài đặt cấu trúc dữ liệu cho bảng danh biểu. Các ô trong mảng symtable là các cặp gồm một con trỏ chỉ đến mảng lexemes và một số nguyên biểu thị cho token được lưu tại vị trí đó. Thủ tục init.c được dùng để khởi gán các từ khóa vào bảng danh biểu. Biểu diễn trị từ vựng và token cho tất cả các từ khóa được lưu trong mảng keywords cùng kiểu với mảng symtable. Hàm init( ) duyệt lần lượt qua mảng keyword, sử dụng hàm insert để đặt các từ khóa vào bảng danh biểu. Thủ tục lỗi error.c Thủ tục này quản lý các ghi nhận lỗi và hết sức cần thiết. Khi gặp một lỗi cú pháp, trình biên dịch in ra một thông báo cho biết rằng một lỗi đã xảy ra trên dòng nhập hiện hành và dừng lại. Một kỹ thuật khắc phục lỗi tốt hơn có thể sẽ nhảy qua dấu chấm phẩy kế tiếp và tiếp tục phân tích câu lệnh sau đó. 2. Cài đặt chương trình nguồn Chương trình nguồn C cài đặt chương trình dịch trên. 39
12. int p, b = 0; while ( isalnum (t) ) { /* t thuộc loại chữ - số */ lexbuf[b] = t; t = getchar ( ); b = b + 1; if (b > = BSIZE) error("compiler error"); } lexbuf[b] = EOS; if (t ! = EOF) ungetc (t, stdin); p = lookup (lexbuf); if (p = = 0) p = insert (lexbuf, ID) tokenval = p; return symtable[p].token; } else if (t = = EOF) { return DONE; else { tokenval = NONE; return t; } } } / parser.c / # include "global.h" int lookahead; parse ( ) /* phân tích cú pháp và dịch danh sách biểu thức */ { lookahead = lexan ( ); while (lookahead ! = DONE) { expr( ) ; match (‘ ; ’); } } expr ( ) { int t; term ( ); while(1) switch (lookahead) { case ' + ' : case ' - ' : t = lookahead; 41
13. emit (t, tval) /* tạo ra kết quả */ int t, tval; { switch ( t ) { case ' + ' : case ' - ' : case ' * ' : case ' / ' : printf (" %c \n", t); break; case DIV : printf (" DIV \n", t); break; case MOD : printf (" MOD \n", t); break; case NUM : printf (" %d \n", tval ); break; case ID : printf (" %s \n", symtable [tval]. lexptr); break; default : printf (" token %d , tokenval %d \n ", t, tval ); } } / symbol.c / # include "global.h" # define STRMAX 999 /* kích thước mảng lexemes */ # define SYMMAX 100 /* kích thước mảng symtable */ char lexemes [STRMAX]; int lastchar = -1 /* vị trí được dùng cuối cùng trong lexemes */ struct entry symtable [SYMMAX]; int lastentry = 0 /* vị trí được dùng cuối cùng trong symtable */ int lookup (s) /* trả về vị trí của ô cho s */ char s [ ]; { int p; for (p = lastentry; p > 0; p = p - 1) if (strcmp (symtable[p].lexptr, s ) = = 0) return p; return 0; } int insert (s, tok) /* trả về vị trí của ô cho s */ char s [ ]; int tok; { int len; len = strlen (s) /* strlen tính chiều dài của s */ 43
14. init ( ); parse ( ); exit (0); /* kết thúc thàình công * / } / / 45
15. 2.6. Yêu cầu như bài 5 cho biểu thức số học ở dạng hậu tố sang dạng trung tố. 2.7. Xây dựng một lược đồ dịch trực tiếp cú pháp để xác định rằng các dấu ngoặc trong một chuỗi nhập là cân bằng. 2.8. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch phát biểu FOR của ngôn ngữ C có dạng như sau: FOR ( exp1; exp2; exp3 ) Stmt sang dạng mà máy ảo kiểu Stack. Viết chương trình thực thi mã máy ảo kiểu Stack . 2.9. Xét đoạn văn phạm sau đây cho các câu lệnh if-then và if-then-else: Stmt → if expr then stmt | if expr then stmt else stmt | other a) Chứng tỏ văn phạm này là văn phạm mơ hồ. b) Xây dựng một văn phạm không mơ hồ tương đương với quy tắc: mỗi else chưa được kết hợp sẽ được kết hợp với then chưa kết hợp gần nhất trước đó. c) Xây dựng một lược đồ dịch trực tiếp cú pháp để dịch các câu lệnh điều kiện thành mã máy ảo kiểu Stack. 2.10. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch các phát biểu của ngôn ngữ PASCAL có dạng như sau sang dạng mà máy ảo kiểu Stack. Viết chương trình thực thi mã máy ảo kiểu Stack: a) REPEAT Stmt UNTIL expr b) IF expr THEN Stmt ELSE Stmt c) WHILE expr DO Stmt d) FOR i := expr1 downto expr2 DO Stmt 47