Đồ án Thiết kế ngôn ngữ lập trình Đơn Giản

MỤC LỤC CHƯƠNG 1 MỞ ĐẦU 1.1 GIỚI THIỆU ĐỀ TÀI Khoa học công nghệ phát triển, đặc biệt là Tin học. Để sớm hiểu biết và phát huy ứng dụng của môn khoa học này, người ta đã đưa Tin học vào giảng dạy cho các em học sinh ở các trường học. Tin học giúp cho học sinh có khả năng phân tích, tổng hợp, khái quát hóa vấn đề và đặc biệt là phát triển tư duy. Tin học giúp cho việc giải quyết các bài toán chính xác, rõ ràng. Không riêng các học sinh phổ thông mà các học sinh tiểu học cũng cần phải học để sớm biết về môn khoa học này. Có thể nói bước đầu để học Tin học là học ngôn ngữ lập trình. Hiện đã có rất nhiều các ngôn ngữ lập trình bậc cao Pascal, C, Foxpro... Các ngôn ngữ này hoàn toàn dùng bằng tiếng Anh, với cấu trúc câu lệnh phức tạp. Đê các em nhỏ làm quen với các ngôn ngữ lập trình này và ứng dụng nó thì thật không đơn giản. Thiết nghĩ đến vấn đề này, trong thời gian thực tập tốt nghiệp, em chọn đề tài “Thiết kế ngôn ngữ lập trình Đơn Giản”, nhằm thiết kế một ngôn ngữ lập trình bằng tiếng Việt, với cấu trúc câu lệnh đơn giản, dễ hiểu nhưng không mất tính tổng quát. Ngôn ngữ này sẽ phần nào giúp cho các em học sinh dễ dàng làm quen với cách lập trình để giải quyết các bài toán trên máy tính. 1.2 QUAN ĐIỂM THIẾT KẾ Việc thiết kế mới một ngôn ngữ là khá phức tạp, song chúng ta có thể dựa vào một số ưu điểm của các ngôn ngữ bậc cao đã có để xây dựng nên một ngôn ngữ thì vấn đề sẽ đơn giản hơn mà vẫn đáp ứng được các yêu cầu của bài toán. Ở đây chúng ta có hai phương pháp để giải quyết: một là tạo trình biên dịch, hai là tạo trình thông dịch. Trình biên dịch (compiler): làm nhiệm vụ chuyển một chương trình viết trong ngôn ngữ cấp cao (chương trình nguồn) sang chương trình trong ngôn ngữ cấp cao khác hoặc ngôn ngữ máy (chương trình đích). Thời gian chuyển một chương trình nguồn sang chương trình đích được gọi là thời gian dịch. Chương trình đích sẽ được thực thi trong thời gian đó được gọi là thời gian thực thi. Như vậy chương trình nguồn và dữ liệu được xử lý trong hai thời gian khác nhau, được gọi là thời gian dịch và thời gian thực thi. Trình thông dịch là quá trình xử lý dạng bên trong của chương trình nguồn và dữ liệu cùng một thời gian. Chương trình thông dịch sẽ phân tích từng phát biểu và thực thi luôn. Đề tài được xây dựng theo phương pháp thông dịch. Với phương pháp tạo trình thông dịch ta có thể định nghĩa chương trình là tập các lệnh. Do đó việc thực hiện một chương trình cũng chính là việc thực hiện từng câu lệnh một. Bài toán đưa về việc giải quyết từng câu lệnh. 1.3 KỸ THUẬT BIÊN DỊCH Khi lập trình trên một ngôn ngữ cấp cao nào đó, có bao giờ bạn tự hỏi nhờ vào đâu mà máy tính có thể hiểu được chương trình mình viết để mà phân tích và cho ra kết quả như vậy không. Chính nhờ vào một chương trình dịch đã viết cho ngôn ngữ đó để dịch chương trình nguồn ra chương trình đích, đây cũng là kết quả của chương trình. Quá trình dịch từ chương trình nguồn ra chương trình đích thường được thực hiện trong nhiều giai đoạn. Chương trình dịch được viết cho ngôn ngữ Đơn Giản ở đây, dựa trên một số kỹ thuật biên dịch của Lý thuyết Trình Biên Dịch, gồm các giai đoạn sau: - Giai đoạn phân tích từ vựng: nhiệm vụ cơ bản của nó là gộp các ký tự thành các từ tố cho bộ phân tích cú pháp. - Giai đoạn phân tích cú pháp: ở giai đoạn này, giải thuật của chương trình là phân tích cú pháp các câu lệnh đồng thời tính toán tạo kết quả cho từng lệnh trong chương trình nguồn. 1.4 CẤU TRÚC ĐỒ ÁN Chương 1: Giới thiệu về mục đích, phương pháp, kỹ thuật xây dựng đề tài và nội dung đồ án. Chương 2: Trình bày phần thiết kế ngôn ngữ Đơn Giản bao gồm cả lý thuyết và bài tập ví dụ. Chương 3: Nêu lên một số kỹ thuật cơ bản để xây dựng chương trình dịch, kỹ thuật này sẽ được áp dụng để thiết kế chương trình cho đồ án. Chương 4: Dựa trên một số kỹ thuật ở chương 3 để thiết kế chương trình dịch cho ngôn ngữ Đơn Giản. Chương 5: Trình bày cách sử dụng chương trình và chạy thử một vài chương trình ví dụ. Chương 6: Tóm tắt kết quả đã đạt được, tính khả thi, hạn chế và nêu lên hướng phát triển của đề tài. CHƯƠNG 2 THIẾT KẾ NGÔN NGỮ ĐƠN GIẢN 2.1 CÁC KHÁI NIỆM CƠ BẢN CỦA NGÔN NGỮ ĐƠN GIẢN Phần này giới thiệu về tập ký tự, biến, hằng, từ khóa, chú thích, biểu thức và các qui tắc sử dụng chúng. 2.1.1 Tập các ký tự hợp lệ trong ngôn ngữ - Các chữ cái: dùng các chữ cái tiếng Việt có dấu hoặc không dấu tùy ý - Các chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 - Ký tự gạch nối: _ - Dấu cách (dùng để phân biệt giữa các từ). 2.1.2 Định danh Định danh là một dãy các ký tự bắt đầu bằng chữ cái, theo sau là chữ cái, dấu gạch dưới hoặc chữ số. Định danh Chữ cái Chữ số _ Chữ cái _ Hình 1.1 Biểu diễn định danh Ví dụ: - Tên đúng: biến_x, biến1, số, abc... - Tên sai: 1ab, 1biến, a b, a#b,... Trong định danh chữ hoa và chữ thường được xem là khác nhau. Nếu dùng một biến chữ thường mà in ra một biến chữ hoa hoặc ngược lại thì chương trình sẽ xem như biến đó có giá trị bằng 0. 2.1.3 Từ khóa Là các từ dành riêng trong ngôn ngữ, mỗi từ có chức năng nhất định, khi sử dụng phải viết đúng cú pháp, không được dùng vào việc đặt tên biến. nếu thì nếu_không trong_khi lặp đến_khi lặp_lại cho tới xuống và hoặc phủ_định 2.1.4 Dấu chấm phẩy, lời giải thích, hằng ký tự - Lời giải thích: Cho phép người lập trình chèn câu ghi chú vào bất kì vị trí nào trong chương trình nhằm mục đích làm sáng tỏ thêm cấu trúc của chương trình mà không ảnh hưởng đến các phần khác. Các lời chú thích được đặt sau dấu ngoặc kép (“). Ví dụ: tổng := a+b; “tính tổng hai số a và b - Dấu ‘;’ Được dùng để phân cách các câu lệnh và không thể thiếu. Ví dụ: a := a+b; c := a+b; - Các hằng ký tự: Các hằng ký tự được biểu diễn trong cặp dấu nháy đơn ‘ ‘ Ví dụ: ‘Chào bạn’ 'Tổng các số dương là: ’ 2.1.5 Phép toán Các ký hiệu toán học + - * / = = () - Phép toán số học: +, - , *, /, div, mod - Phép toán quan hệ: , >=, - Phép toán logic: và, hoặc - Toán tử gán: := Ví dụ: a:=b+1; x1:=(-b+căn_bh(delta))/2*a; 2.1.6 Biểu thức Biểu thức là một công thức tính toán để có một giá trị theo một qui tắc toán học nào đó. Một biểu thức bao gồm toán tử và toán hạng. Toán tử được viết bằng dấu các phép toán. Toán hạng có thể là hằng, hàm, là biến. Các phần tử của biểu thức có thể được phân thành toán hạng, thừa số, biểu thức đơn giản. Một biểu thức có chứa các toán tử quan hệ được gọi là biểu thức quan hệ. Ví dụ: 9+căn_bh(a); (a+b)*5-c; biểu thức a = c biểu thức quan hệ (biểu thức boolean đơn giản) (a0) và (d>0) biểu thức boolean 2.2 SƠ ĐỒ CÚ PHÁP chương trình lệnh ; lệnh lệnh gán lệnh cho lệnh trong_khi lệnh nếu lệnh lặp_lại { } lệnh lệnh lặp_lại lệnh đến_khi btqh lặp_lại ; lệnh trong_khi btqh lặp lệnh trong_khi lệnh nếu nếu btqh thì lệnh nếu_không lệnh lệnh cho cho := định danh biểu thức đến xuống biểu thức lặp lệnh định danh biểu thức lệnh gán := <= > >= = < biểu thức quan hệ biểu thức biểu thức btqh ( và hoặc btqh ) phủ_định btqh btqh hạng thức số hạng div * / mod số hạng số hạng biểu thức ( định danh hằng ) biểu thức + - hạng thức + - hạng thức Hình 1.2 Dãy sơ đồ biểu diễn cú pháp của ngôn ngữ Đơn Giản 2.3 CÁC CẤU TRÚC LỆNH Chương trình đã sử dụng 3 loại cấu trúc cơ bản là tuần tự, rẽ nhánh và lặp. 2.3.1 Cấu trúc tuần tự Cấu trúc tuần tự là cấu trúc mà máy thực hiện liên tục từ lệnh đầu tiên đến lệnh cuối cùng của chương trình. 2.3.2 Cấu trúc rẽ nhánh Cú pháp: nếu thì nếu_không Nếu dãy lệnh nhiều hơn hai lệnh thì phải đặt giữa hai dấu ngoặc nhọn “{“ và “}”. Khi gặp lệnh này, máy kiểm tra điều kiện logic. Nếu điều kiện logic đúng (khác 0) thì thực hiện . Còn nếu điều kiện logic sai (bằng 0) thì thực hiện (khi có nếu_không) hoặc bỏ qua cấu trúc này (nếu không có nếu_không). Có thể có nhiều cấu trúc nếu...thì...nếu_không lồng nhau nhưng không được cắt nhau. Ví dụ: “Giải phương trình bậc hai sau đây: xóa_mh(); viết_xd(‘Nhập các hệ số a,b,c’) đọc_xd(a,b,c); nếu (a=0) thì { nếu (b=0) thì { nếu (c=0) thì viết_xd(‘phương trình vô định’) } nếu_không viết_xd(‘phương trình có nghiệm duy nhất=’, -c/b); nếu_không { delta:= b*b-4*a*c; nếu (d=0) thì { viết_xd(‘phương trình có nghiệm kép); viết(‘x1=x2 =’-b/2*a); } nếu_không nếu (delta<0) thì viết_xd(‘phương trình vô nghiệm’); nếu_không { viết_xd(‘phươngtrình có hai nghiệm’); viết_xd (‘ x1= ’, -b - sqrt(delta)/(2*a)); viết_xd (‘ x1= ’, -b + sqrt(delta)/(2*a)); } đọc_xd(); Kết quả: Nhập các hệ số a, b, c: -1 4 1 Phương trình có hai nghiệm x1=-0,236068 x2=4,23607 2.3.3 Cấu trúc lặp a. Lệnh lặp trong_khi Cú pháp: trong_khi lặp Chừng nào còn đúng thì còn được thực hiện. Mỗi lần thực hiện xong , sẽ được kiểm tra, nếu còn đúng tiếp tục được thực hiện, nếu sai lệnh tiếp theo được thực hiện. Ví dụ: “Chương trình tính tổng bình phương các số “s:=12+22+32+...+n2 viết_xd(‘CHƯƠNG TRÌNH TÍNH TỔNG BÌNH PHƯƠNG’); viết(‘ Bạn muốn nhập bao nhiêu số:’); đọc_xd(n); s:=0; i:=1; trong_khi(i<=n) lặp { s:=s+(i*i); i:=i+1; } viết_xd(‘Tổng bình phương của:’,n,’ số là: ‘,s); đọc_xd(); Kết quả: Bạn muốn nhập bao nhiêu số: 5 Tổng bình phương của 5 số là:55 b. Lệnh lặp lặp_lại Câu lệnh lặp_lại ... đến_khi là câu lệnh yêu cầu chương trình thực hiện lặp lại nhiều lần một số hành động đến khi thỏa mãn điều kiện thoát của vòng lặp. Cú pháp: lặp_lại đến_khi Chừng nào còn sai thì dãy lệnh được thực hiện. Mỗi khi thực hiện xong , sẽ được kiểm tra, nếu đúng chuyển sang thực hiện lệnh tiếp theo, nếu không lại được tiếp tục thực hiện. Ví dụ: “Tính tổng s:=1+2+3+...+ n xóa_mh(); viết_xd('Nhập bao nhiêu sô:'); đọc_xd(n); i:=1; s:=0; lặp_lại { s:=s+i; i:=i+1; } đến_khi(i>=n); viết_xd('Tổng các chư số đó là:',s); đọc_xd(); Kết quả: Nhập bao nhiêu số: 5 Tổng các chữ số đó là: 15 c. Lệnh lặp cho Câu lệnh lặp cho là câu lệnh làm cho chương trình thực hiện lặp lại một số hành động một số lần nhất định. Cú pháp: cho = tới lặp hoặc cho : xuống lặp Số lần thực hiện câu lệnh do qui định, biến này được gán giá trị đầu là sau mỗi lần thực hiện biến điều khiển sẽ tăng lên hoặc giảm xuống một đơn vị, tiếp tục thực hiện cho đến khi biến điều khiển vượt quá Ví dụ: “Tính tổng xóa_mh(); viết_xd ('Nhập giá trị của n :'); đọc_xd(n); i:=0; s:=0; cho i=1 tới n lặp s:=s+i; viết_xd(‘Kết quả là:’,s); đọc_xd(); Kết quả: Nhập giá trị n: 9 Kết quả đó là: 45 2.4 BỘ LỆNH Lệnh là một chỉ thị yêu cầu máy thực hiện một thao tác nào đó. Lệnh đơn là lệnh không chứa lệnh nào khác. Lệnh ghép là lệnh ghép nhiều lệnh lại với nhau thành chung một lệnh bằng cách đặt giữa hai dấu ngoặc nhọn “{“ và “}”. Các lệnh viết ngăn cách nhau bởi dấu “;” và trên một dòng có thể viết nhiều lệnh. Về kiểu dữ liệu thì chương trình nhận kiểu số thực. 2.4.1 Lệnh gán biến:=biểu_thức; Tính giá trị của biểu thức bên phải rồi gán cho biến bên trái Ví dụ: a:=10; b:=8*(a+25)-5; 2.4.2 Các lệnh vào ra dữ liệu a. Lệnh in lên màn hình: (1) viết( ’st1’,bt1, ’st2’,bt2,’st3’,bt3...,’stn’,btn); (2) viết_xd(’st1’,bt1, ’st2’,bt2,’st3’,bt3...,’stn’,btn); (3) viết_xd(‘’); Dạng (1): In các chuỗi và giá trị của các biểu thức ra màn hình, in xong không xuống dòng. Dạng (2): In các chuỗi và giá trị của các biểu thức ra màn hình, in xong xuống dòng. Dạng (3): Không in gì cả và xuống dòng. Ví dụ: viết(‘a=’, a,’b=’,b); viết_xd(); hay viết_xd(‘a+b=’,c); b. Lệnh nhập dữ liệu từ bàn phím (1) đọc(biến) (2) đọc_xd(biến1, biến2, ..., biếnN); (3) đọc_xd(); Dạng (1): Máy sẽ nhận ngay ký tự nhập vào và gán cho biến mà không chờ nhấn ENTER. Dạng (2): Máy chờ người dùng nhập dữ liệu từ bàn phím, các dữ liệu này ngăn cách nhau ít nhất một ký tự trống nếu trong lệnh có nhiều biến, rồi nhấn ENTER để kết thúc việc nhập. Sau đó máy sẽ lần lược lấy giá trị nhập vào để gán cho các biến tương ứng. Biến nhận giá trị thuộc kiểu thực. Dạng (3): Chờ người dùng nhấn phím ENTER để tiếp tục thực hiện chương trình. 2.4.3 Các lệnh điều khiển a. Xóa màn hình xóa_mh(); Xóa sạch màn hình trước khi in ra kết quả. b.Tạo cửa sổ cửa_sổ(x1, y1, x2, y2); Tạo cửa sổ có tọa độ góc trên bên trái x1, y1 và tọa độ góc dưới bên phải x2, y2. c. Đặt màu chữ, màu nền màu_chữ(color); màu_nền(color); Trong hai trường hợp trên color là một biến nguyên chứa mã của màu (xem bảng2.1) Ví dụ: màu_chữ(4) chữ in ra sẽ là màu đỏ màu_nền(1) màu của nền sẽ là màu xanh da trời d. Di chuyển con trỏ đến(x, y) Di chuyển con trỏ đến tạo độ x, y của màn hình tương ứng với cửa sổ hiện tại. e. Các lệnh về âm thanh âm_thanh(f); Tạo tín hiệu âm thanh với tần số f. tắt(); Tắt tín hiệu âm thanh. f. Lệnh trễ chương trình chờ(ms); Làm trễ chương trình một khoảng thời gian miligiây 2.4.4 Các hàm toán học a. Tính căn bậc hai của x căn_bh(x); Hàm này tính căn bậc hai của biến số x, với x là một số bất kì lớn hơn 0 b. Hàm tính giá trị tuyệt đối của x trị_td(x); Hàm này tính trị tuyệt đối của biến số x c. Các hàm tính sin(x), cos(x), tg(x) sin(x); cos(x); tg(x); 2.4.5 Các hàm vẽ đồ họa Các hàm vẽ đồ họa đơn giản có màu nét vẽ được xác định bởi hàm màu_vẽ(tên màu), với tên màu là các số trong bảng màu 2.1. a. Hàm vẽ đường thẳng đ_thẳng(x1, y1, x2, y2); Vẽ một đường thẳng xác định với tọa độ điểm đầu là (x1,y1) tọa độ điểm cuối là (x2,y2). b. Hàm vẽ hình chữ nhật hình_cn(x1, y1, x2, y2); Tọa độ đỉnh trên bên trái (x1,y1), tọa độ đỉnh dưới bên phải (x2,y2). c. Hàm vẽ đường tròn đ_tròn(x, y, r); Tọa độ tâm của đường tròn (x,y), bán kinh đường tròn r d. Hàm vẽ elip elip(x, y, gd, gc, xr, yr); (x,y) là tọa độ của tâm elip gd là góc đầu gd là góc cuối xr là bán trục ngang, yr là bán trục đứng. Tên màu Giá trị số (mã màu) Màu chữ hay màu nền Đen 0 Cả hai Xanh da trời 1 Cả hai Xanh lá cây 2 Cả hai Xanh lơ 3 Cả hai Đỏ 4 Cả hai Tím 5 Cả hai Nâu 6 Cả hai Xám nhạt 7 Cả hai Xám sẫm 8 Màu chữ Xanh nhạt 9 Màu chữ Xanh nhạt 10 Màu chữ Xanh nhạt 11 Màu chữ Đỏ nhạt 12 Màu chữ Tím nhạt 13 Màu chữ Vàng 14 Màu chữ Trắng 15 Màu chữ Bảng 2.1 Bảng màu CHƯƠNG 3 ÁP DỤNG MỘT SỐ KỸ THUẬT BIÊN DỊCH CƠ BẢN Chương này sẽ trình bày các bước cơ bản để xây dựng một chương trình dịch nhằm làm cơ sở lý thiết để xây dựng chương trình trong chương tiếp theo. 3.1 PHÂN TÍCH TỪ VỰNG Phân tích từ vựng là giai đoạn đầu của quá trình biên dịch. Nhiệm vụ chủ yếu của nó là đọc các ký tự nhập rồi tạo ra một chuỗi thẻ từ cho bộ phân tích cú pháp sử dụng trong giai đoạn phân tích cú pháp. Tương tác giữa bộ phân tích từ vựng và bộ phân tích cú pháp minh họa (hình 3.1), được cài đặt bằng cách cho bộ phân tích từ vựng làm một thủ tục con hoặc một đồng thủ tục với bộ phân tích cú pháp. chương trình nguồn bộ phân tích từ vựng bảng ký hiệu thẻ từ lấy thẻ từ kế tiếp Hình 3.1 Tương tác của bộ phân tích từ vựng và bộ phân tích cú pháp bộ phân tích cú pháp Khi nhận được yêu cầu lấy thẻ từ tiếp theo từ bộ phân tích cú pháp, bộ phân tích từ vựng sẽ đọc các ký tự cho đến khi nó nhận diện ra được một thẻ từ. Bộ phân tích từ vựng là thành phần đọc chương trình nguồn của trình biên dịch, nó thường thực hiện thêm một số tác vụ khác ở mức giao diện người sử dụng như sau: 3.1.1 Loại bỏ khoảng trắng và các dòng chú thích Chương trình dịch sẽ xét các ký tự trong nguyên liệu, vì thế các ký tự ngoài dự kiến như các ký tự trống sẽ khiến nó thất bại. Ngôn ngữ lập trình thường cho phép các khoảng trắng (ký tự trống, ký tự tab, ký tự xuống dòng) xuất hiện giữa các thẻ từ. Bộ phân tích từ vựng có nhiệm vụ loại bỏ các khoảng trắng này trước khi đưa qua bộ phân tích cú pháp. Các dòng chú thích cũng được bộ phân tích cú pháp và chương trình dịch bỏ qua, vì thế chúng cũng được xử lý như khoảng trắng. 3.1.2 Các hằng Mỗi khi có một ký số xuất hiện trong một biểu thức, có lẽ sẽ hợp lý hơn khi cho phép đặt một hằng số nào đó ở vị trí của nó. Bởi vì một hằng số là một dãy các ký số, nó có thể dùng được bằng cách thêm các luật sinh vào văn phạm cho các biểu thức hoặc bằng cách tạo ra một thẻ từ cho các hằng như thế. Công việc gom các ký số thành số, được thực hiện bởi bộ phân tích từ vựng bởi vì các số có thể được xử lý như những đơn vị riêng biệt trong quá trình dịch. Chẳng hạn num là thẻ từ biểu thị một số thì bộ phân tích từ vựng sẽ chuyển num cho bộ phân tích cú pháp. Giá trị của số sẽ được chuyển theo dưới dạng một thuộc tính của thẻ từ num, bộ phân tích từ vựng sẽ chuyển cả thẻ từ và thuộc tính của nó cho bộ phân tích cú pháp. Nếu ta viết một thẻ từ và thuộc tính của nó như một bộ dữ liệu được bao giữa hai dấu thì nguyên liệu 25.5 + 90 - 20 được biến đổi thành một dãy các bộ Thẻ từ +,- không có thuộc tính. Thành phần thứ hai của các bộ không có vai trò gì trong khi phân tích cú pháp nhưng sẽ cần dùng đến khi dịch. 3.1.3 Nhận diện định danh và từ dành riêng Ngôn ngữ sử dụng định danh làm tên cho các biến. Một văn phạm cho một ngôn thường xử lý định danh như một thẻ từ. Bộ phân tích cú pháp dựa trên một văn phạm, như thế muốn nhận được cùng một thẻ từ chẳng hạn là id, mỗi khi có một định danh xuất hiện trong nguyên liệu. Ví dụ: a:= a+ b; sẽ được bộ phân tích từ vựng biến đổi thành dòng thẻ từ id = id + id Khi gặp một từ tố tạo ra một định danh trong nguyên liệu, thì ta cần có một cơ chế xem từ tố này đã gặp trước đó hay chưa. Ta sẽ dùng một bảng ký hiệu cho công việc này. Từ tố lưu trong bảng ký hiệu và một con trỏ chỉ đến mục ghi trên bảng trở thành một thuộc tính của thẻ từ id. Ngoài định danh còn có các từ khóa, các tên hàm là các từ dành riêng, các định danh không được trùng tên với các từ này. Bộ phân tích từ vựng xác định định danh hay từ dành riêng bằng cách sau khi gom thành thẻ từ rồi so sánh với các từ dành riêng trong bảng ký hiệu nếu không trùng thì thẻ từ đó là id, ngược lại là từ dành riêng. 3.1.4 Giao diện cho bộ phân tích từ vựng Khi một bộ phân tích từ vựng được đặt giữa bộ phân tích cú pháp và dòng nguyên liệu, nó tương tác với cả hai phần này như (hình 3.2). Nó đọc các ký tự từ nguyên liệu, nhóm chúng lại thành các từ tố rồi gửi các thẻ từ được tạo bởi các từ tố cùng với giá trị thuộc tính của chúng đến giai đoạn sau của trình biên dịch. Trong một số tình huống, bộ phân tích từ vựng phải đọc trước một ký tự trước khi có thể quyết định sẽ trả về thẻ từ nào cho bộ phân tích cú pháp. Ví dụ: Khi gặp ký tự > thì bộ phân tích từ vựng sẽ đọc tiếp. Nếu ký tự kế tiếp là = thì chuỗi ký tự >= là từ tố tạo ra thẻ từ cho toán tử “lớn hơn hoặc bằng”. Ngược lại thì > là từ tố tạo ra thẻ từ cho toán tử “lớn hơn”, và bộ phân tích từ vựng đã đọc một ký tự nhiều lần. Ký tự “dư” ra này phải được đưa trở lại nguyên liệu, bởi vì nó có thể là ký từ đầu tiên của từ tố kế tiếp trong nguyên liệu. nguyên liệu truyền thẻ từ và thuộc tính đọc kí tự đẩy kí tự trở về bộ phân tích từ vựng Hình 3.2 Đặt bộ phân tích từ vựng vào giữa nguyên liệu và bộ phân tích cú pháp bộ phân tích cú pháp Bộ phân tích từ vựng tạo ra các thẻ từ và bộ phân tích cú pháp sẽ sử dụng nó. Các thẻ từ sinh ra được giữ trong vùng đệm cho đến khi chúng được sử dụng. Tương tác giữa hai bộ phân tích này chỉ bị ràng buộc bởi kich thước vùng đệm bởi vì bộ phân tích từ vựng sẽ không thể tiến hành khi vùng đệm đầy còn bộ phân tích cú pháp sẽ không thể tiến hành khi vùng đệm rỗng. Vì vùng đệm chỉ giữ một thẻ từ nên tương tác được cài đặt đơn giản bằng cách đưa bộ phân tích từ vựng thành một hàm được bộ phân tích cú pháp gọi, trả về các thẻ từ theo như yêu cầu. 3.2 ĐỊNH NGHĨA CÚ PHÁP Trong phần này sẽ giới thiệu một hệ ký pháp có tên gọi là văn phạm phi ngữ cảnh được dùng để xác định cú pháp của một ngôn ngữ. Một văn phạm thường mô tả cấu trúc phân cấp của nhiều kết cấu của các ngôn ngữ lập trình. Ví dụ: Một câu lệnh trong C có dạng: if (biểu_thức) lệnh else lệnh Có nghĩa là một phép nối của từ khóa if, một dấ