Thiết kế trình biên dịch - Trình phân tích cú pháp từ dưới lên

Phân tích cú pháp từ dưới lên bắt đầu từ các nút lá của cây và hoạt động theo hướng đi lên cho đến khi nó đến nút gốc. Ở đây, chúng ta bắt đầu từ một câu và sau đó áp dụng các quy tắc sản xuất theo cách ngược lại để đạt được biểu tượng bắt đầu. Hình ảnh dưới đây mô tả các trình phân tích cú pháp từ dưới lên có sẵn.

Shift-Reduce Parsing

Phân tích cú pháp Shift-Reduce sử dụng hai bước duy nhất để phân tích cú pháp từ dưới lên. Các bước này được gọi là bước chuyển và bước giảm.

Shift step: Bước dịch chuyển đề cập đến sự tiến của con trỏ đầu vào tới ký hiệu đầu vào tiếp theo, được gọi là ký hiệu đã dịch chuyển. Biểu tượng này được đẩy lên ngăn xếp. Biểu tượng được dịch chuyển được coi như một nút duy nhất của cây phân tích cú pháp.
Reduce step: Khi trình phân tích cú pháp tìm thấy một quy tắc ngữ pháp hoàn chỉnh (RHS) và thay thế nó thành (LHS), nó được gọi là bước rút gọn. Điều này xảy ra khi trên cùng của ngăn xếp có một chốt. Để giảm bớt, một chức năng POP được thực hiện trên ngăn xếp bật ra khỏi tay cầm và thay thế nó bằng biểu tượng không đầu cuối LHS.

Trình phân tích cú pháp LR

Trình phân tích cú pháp LR là trình phân tích cú pháp không đệ quy, shift-giảm, từ dưới lên. Nó sử dụng nhiều loại ngữ pháp không có ngữ cảnh, làm cho nó trở thành kỹ thuật phân tích cú pháp hiệu quả nhất. Bộ phân tích cú pháp LR còn được gọi là bộ phân tích cú pháp LR (k), trong đó L là viết tắt của việc quét từ trái sang phải của luồng đầu vào; R là viết tắt của việc xây dựng đạo hàm bên phải ngược lại, và k biểu thị số ký hiệu nhìn trước để đưa ra quyết định.

Có ba thuật toán được sử dụng rộng rãi có sẵn để xây dựng trình phân tích cú pháp LR:

SLR (1) - Trình phân tích cú pháp LR đơn giản:
- Làm việc trên lớp ngữ pháp nhỏ nhất
- Rất ít trạng thái, do đó bảng rất nhỏ
- Thi công đơn giản và nhanh chóng
LR (1) - Bộ phân tích cú pháp LR:
- Làm việc trên bộ hoàn chỉnh LR (1) Ngữ pháp
- Tạo bảng lớn và số lượng lớn các trạng thái
- Thi công chậm
LALR (1) - Trình phân tích cú pháp LR Nhìn trước:
- Hoạt động trên kích thước trung bình của ngữ pháp
- Số trạng thái giống như trong SLR (1)

Thuật toán phân tích cú pháp LR

Ở đây chúng tôi mô tả thuật toán khung của trình phân tích cú pháp LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL so với LR

LL	LR
Có một dẫn xuất ngoài cùng bên trái.	Có một dẫn xuất ngoài cùng bên phải ngược lại.
Bắt đầu với danh nghĩa gốc trên ngăn xếp.	Kết thúc với danh nghĩa gốc trên ngăn xếp.
Kết thúc khi ngăn xếp trống.	Bắt đầu với một ngăn xếp trống.
Sử dụng ngăn xếp để chỉ định những gì vẫn được mong đợi.	Sử dụng ngăn xếp để chỉ định những gì đã thấy.
Xây dựng cây phân tích cú pháp từ trên xuống.	Xây dựng cây phân tích cú pháp từ dưới lên.
Liên tục bật một danh nghĩa ra khỏi ngăn xếp và đẩy phía bên tay phải tương ứng.	Cố gắng nhận ra một phía bên phải trên ngăn xếp, bật nó ra và đẩy danh nghĩa tương ứng.
Mở rộng các thiết bị đầu cuối.	Giảm các thiết bị đầu cuối.
Đọc các thiết bị đầu cuối khi nó bật một đầu ra khỏi ngăn xếp.	Đọc các thiết bị đầu cuối trong khi nó đẩy chúng vào ngăn xếp.
Đặt trước trình duyệt của cây phân tích cú pháp.	Duyệt theo thứ tự của cây phân tích cú pháp.