sự khác biệt giữa lex và yacc

Question

Tôi đã làm việc với lex để thực thi một số mã bất cứ khi nào một số cụm từ thông dụng được tìm thấy, Yacc có thể làm điều gì đó hơn thế không? Nếu có, thì sao?

Answer 1

Lex là một công cụ để xây dựng các máy phân tích từ vựng, có thể thực hiện một số công cụ từ vựng khá ngu ngốc (như tìm từ khóa). Yacc là trình tạo trình phân tích cú pháp, có thể tạo các trình phân tích cú pháp cho các ngôn ngữ máy tính thực. Phân tích của nó thường dựa trên đầu ra của lex (đó là một dòng mã thông báo) và từ đó có thể tạo ra phân tích cú pháp của cây của ngôn ngữ lập trình - cái gì đó nhiều hơn lex.

Theo truyền thống, các nhà xây dựng trình biên dịch phân biệt giữa phân tích từ vựng và cú pháp - đó là hai bước quan trọng trong trình biên dịch (các bước tiếp theo ví dụ: tạo mã, tối ưu hóa).

Answer 2

Có, YACC là một trình phân tích cú pháp, Lex là một trình phân tích từ vựng. Chúng thường được sử dụng cùng nhau: bạn Lex đầu vào chuỗi, và YACC đầu vào tokenized được cung cấp bởi Lex.

Hiện tại, cụm từ thông dụng chỉ có thể thể hiện các ngôn ngữ thông thường. Một trong những hạn chế của một ngôn ngữ thông thường là thiếu "bộ nhớ". Bạn không thể xác định các quy tắc cho chấp nhận tiếp tục xuống chuỗi dựa trên những gì đã đến trước đó.

Điều này chủ yếu được nhìn thấy rõ ràng trong trường hợp dấu ngoặc đơn. Ngôn ngữ thông thường không thể khớp với dấu ngoặc đơn lồng nhau với cấp chính xác. Hoặc bất kỳ cấu trúc nào khác như vậy. Các ngữ pháp của (hầu hết) các ngôn ngữ máy tính có thể làm và, do đó, chúng không thể được phân tích cú pháp bằng một biểu thức chính quy hoặc một biểu thức chính quy. Đó là nơi YACC đến.

Người ta cũng có thể đảo ngược câu hỏi. Nếu YACC có thể làm được nhiều hơn, tại sao không sử dụng nó để phân tích từ vựng? Vâng, nó như vậy sẽ xảy ra mà bạn có thể xác minh tính hợp lệ của một biểu thức chính quy rất hiệu quả, mà không phải là trường hợp của các ngữ pháp chung - không cùng cấp. Tuy nhiên, YACC có thể thực hiện phân tích từ vựng cơ bản, nếu các quy tắc ngôn ngữ của ngôn ngữ đủ đơn giản.

Answer 3

lex là lexical analyzer. Nó chia nhỏ văn bản thành các thẻ. Sức mạnh của nó gần tương đương với biểu thức chính quy. yacc là parser generator. Nó có một chuỗi các thẻ (nói, từ lex) và diễn giải chúng như là một loạt các câu lệnh. Sức mạnh của nó tương đương với ngữ pháp tự do ngữ cảnh.

Một ứng dụng điển hình của lex và yacc là để triển khai ngôn ngữ lập trình. lex tokenizes đầu vào, phá vỡ nó thành các từ khóa, hằng số, dấu chấm câu, vv yacc sau đó thực hiện ngôn ngữ máy tính thực tế; công nhận một tuyên bố cho, ví dụ, hoặc một định nghĩa chức năng.

Trong ý nghĩa thực tế, bạn thường sử dụng lex để xử lý văn bản đầu vào thành các đoạn. Sau đó, bạn sử dụng yacc để chuỗi những đoạn đó lại với nhau và xử lý chúng thành một số ý nghĩa lớn hơn.

Answer 4

lex dùng để nhập mã thông báo. Tức là, tách đầu vào của bạn thành các đối tượng cấp thấp nhất mà ngữ pháp của bạn xác định. Ví dụ: bạn sử dụng lex để xác định từ khóa, số nhận dạng, chuỗi, nhận xét, khoảng trắng, v.v.

yacc là để phân tích cú pháp ngữ pháp của bạn. Ngữ pháp là một mô tả ngôn ngữ của bạn, thường được định nghĩa trong EBNF hoặc một số ngữ pháp ngữ cảnh khác. Khi bạn mô tả ngữ pháp của mình thành yacc, bạn có thể sử dụng nó để chạy các hành động của công cụ của bạn khi các phần tử của ngôn ngữ được nhận ra. Ví dụ, điều này có thể là xây dựng các cây cú pháp để giải thích biểu thức, xác định các đối tượng phạm vi, ghi lại các defintions biến và vv.

Chúng là các sản phẩm miễn phí.

Answer 5

lex và yacc thường được sử dụng cùng nhau. Đây là cách bạn thường xây dựng một ứng dụng sử dụng cả hai:

Input Stream (ký tự) -> Lex (tokens) -> Yacc (Abstract Syntax Tree) -> Applcation bạn

Tổng quát hơn, những gì Lex sẽ làm là đọc một tệp nguồn, ngay từ đầu và cố gắng kết hợp một số biểu thức chính quy (lex có cú pháp riêng, đặc biệt của nó, khác với các biểu thức chính quy của perl hoặc sed), và sau đó sẽ gọi một chương trình khác với mỗi mã thông báo mà nó nhận ra. Các thẻ có thể chỉ là một giá trị được liệt kê đơn giản, giống như một từ khóa hoặc toán tử hoặc có thể có một số siêu dữ liệu được đính kèm, giống như một giá trị bằng chữ.

Lex thường (mặc dù không cần thiết) được sử dụng để gọi Yacc. Yacc sử dụng một thuật toán phân tích cú pháp LALR, mà gần như nói, hoạt động bằng cách đẩy mỗi mã thông báo vào một ngăn xếp. Nếu ngăn xếp có một chuỗi mã thông báo mà nó nhận ra, nó sẽ bật tất cả các thẻ, thực hiện một hành động và đẩy một mã thông báo khác trở lại trên ngăn xếp.

Từ vựng thích hợp cho những gì Yacc hoạt động trên thực tế là thiết bị đầu cuối và không phải thiết bị đầu cuối. Một thiết bị đầu cuối là một mã thông báo mà nó nhận được từ chương trình gọi (thường là Lex), và một thiết bị đầu cuối không là kết quả của việc khớp một chuỗi trên ngăn xếp của nó.

Thông thường các hành động được thực hiện theo quy tắc Yacc hoặc là để đánh giá kết quả của phép tính mà quy tắc tương ứng hoặc tạo ra biểu diễn trung gian, như cây cú pháp, để xử lý lớp ứng dụng khác.

Yacc, như lex, có thể được sử dụng riêng biệt với nhau. Ví dụ: bạn có thể sử dụng Yacc bằng cách chuyển các ký tự riêng lẻ từ văn bản nguồn và sử dụng các quy tắc Yacc để nhận ra từng loại mã thông báo. Tuy nhiên Yacc không được thiết kế rất dễ sử dụng theo cách đó, và do đó kết quả lexer sẽ phức tạp hơn nhiều so với một lexer tương đương trong Lex. Một cách sử dụng điển hình hơn là tạo một lexer được mã hóa bằng tay vì các lý do về hiệu suất hoặc vì bạn cần một từ vựng thông minh hơn. Một ví dụ phổ biến của trường hợp thứ hai là được sử dụng trong các ngôn ngữ giống như C mà phải biết về việc sử dụng các số nhận dạng trước đó để biết chúng có được sử dụng để mô tả các loại hoặc các biến hay không.