Phân tích từ điển – Wikipedia

Trong khoa học máy tính, phân tích từ vựng lexing hoặc tokenization là quá trình chuyển đổi một chuỗi các ký tự (như trong chương trình máy tính hoặc trang web ) thành một chuỗi các mã thông báo (chuỗi có nghĩa được gán và do đó được xác định). Một chương trình thực hiện phân tích từ vựng có thể được gọi là máy quét mã thông báo [1] hoặc máy quét mặc dù cũng là một thuật ngữ cho giai đoạn đầu tiên của một lexer. Một lexer thường được kết hợp với một trình phân tích cú pháp, cùng nhau phân tích cú pháp của ngôn ngữ lập trình, trang web, v.v.

Ứng dụng [ chỉnh sửa ]

Một lexer tạo thành giai đoạn đầu tiên của một trình biên dịch trong xử lý hiện đại. Phân tích thường xảy ra trong một lần.

Trong các ngôn ngữ cũ hơn như ALGOL, giai đoạn ban đầu thay vào đó là tái cấu trúc dòng, thực hiện unstropping và loại bỏ khoảng trắng và nhận xét (và có trình phân tích cú pháp không quét, không có từ vựng riêng biệt). Các bước này hiện được thực hiện như một phần của lexer.

Trình phân tích cú pháp và trình phân tích cú pháp thường được sử dụng nhất cho trình biên dịch, nhưng có thể được sử dụng cho các công cụ ngôn ngữ máy tính khác, chẳng hạn như máy in đẹp hoặc máy in. Lexing có thể được chia thành hai giai đoạn: quét phân đoạn chuỗi đầu vào thành các đơn vị cú pháp được gọi là từ vựng và phân loại chúng thành các lớp mã thông báo; và đánh giá trong đó chuyển đổi các từ vựng thành các giá trị được xử lý.

Các trình phân tích nói chung khá đơn giản, với hầu hết sự phức tạp được chuyển đến các giai đoạn phân tích cú pháp hoặc phân tích ngữ nghĩa và thường có thể được tạo bởi một trình tạo lexer, đặc biệt là lex hoặc dẫn xuất. Tuy nhiên, các từ vựng đôi khi có thể bao gồm một số phức tạp, chẳng hạn như xử lý cấu trúc cụm từ để làm cho đầu vào dễ dàng hơn và đơn giản hóa trình phân tích cú pháp và có thể được viết một phần hoặc hoàn toàn bằng tay, để hỗ trợ nhiều tính năng hơn hoặc cho hiệu suất.

Một lexeme là một chuỗi các ký tự trong chương trình nguồn khớp với mẫu của mã thông báo và được phân tích từ vựng xác định là một ví dụ của mã thông báo đó. [2]

Một số tác giả gọi đây là "mã thông báo", sử dụng "mã thông báo" có thể hoán đổi cho nhau để biểu thị chuỗi được mã hóa và cấu trúc dữ liệu mã thông báo dẫn đến việc đưa chuỗi này qua quy trình mã thông báo. [3] [4]

Từ vựng trong khoa học máy tính được định nghĩa khác với từ vựng trong ngôn ngữ học. Một từ vựng trong khoa học máy tính gần tương ứng với những gì có thể được gọi là một từ trong ngôn ngữ học (thuật ngữ từ trong khoa học máy tính có một ý nghĩa khác với từ trong ngôn ngữ học), mặc dù trong một số trường hợp, nó có thể giống với một hình thái hơn.

Mã thông báo từ vựng hoặc đơn giản là mã thông báo là một chuỗi có ý nghĩa được gán và do đó được xác định. Nó được cấu trúc như một cặp bao gồm tên mã thông báo và giá trị mã thông báo tùy chọn . Tên mã thông báo là một danh mục của đơn vị từ vựng. [2] Tên mã thông báo phổ biến là

  • mã định danh: đặt tên cho lập trình viên chọn;
  • từ khóa: tên đã có trong ngôn ngữ lập trình;
  • dấu phân cách (còn được gọi là dấu chấm câu): ký tự dấu chấm câu và dấu phân cách ghép nối; toán tử
  • và tạo ra kết quả;
  • bằng chữ: số, logic, văn bản, chữ tham chiếu;
  • nhận xét: dòng, khối.
Ví dụ về các giá trị mã thông báo
Tên mã thông báo Giá trị mã thông báo mẫu
mã định danh x màu UP
từ khóa nếu trong khi return
dải phân cách } (;
toán tử + , =
nghĩa đen đúng 6.02e23 "âm nhạc"
] / * Truy xuất dữ liệu người dùng * / // phải âm

Hãy xem xét biểu thức này trong ngôn ngữ lập trình C:

x = a + b * 2 ;

Phân tích từ vựng của biểu thức này mang lại chuỗi mã thông báo sau:

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

Tên mã thông báo là tên có thể được gọi là một phần của lời nói trong ngôn ngữ học.

Ngữ pháp từ điển [ chỉnh sửa ]

Đặc tả của ngôn ngữ lập trình thường bao gồm một bộ quy tắc, ngữ pháp từ vựng, xác định cú pháp từ vựng. Cú pháp từ vựng thường là một ngôn ngữ thông thường, với các quy tắc ngữ pháp bao gồm các biểu thức chính quy; họ xác định tập hợp các chuỗi ký tự có thể (từ vựng) của mã thông báo. Một lexer nhận ra các chuỗi và đối với mỗi loại chuỗi được tìm thấy, chương trình từ vựng sẽ thực hiện một hành động, đơn giản nhất là tạo ra một mã thông báo.

Hai loại từ vựng phổ biến quan trọng là khoảng trắng và bình luận. Những điều này cũng được định nghĩa trong ngữ pháp và được xử lý bởi nhà từ vựng, nhưng có thể bị loại bỏ (không tạo ra bất kỳ mã thông báo nào) và được coi là không có ý nghĩa nhiều nhất là tách hai mã thông báo (như trong nếu x ] thay vì ifx ). Có hai ngoại lệ quan trọng cho việc này. Đầu tiên, trong các ngôn ngữ quy tắc bên ngoài phân định các khối có thụt lề, khoảng trắng ban đầu rất quan trọng, vì nó xác định cấu trúc khối và thường được xử lý ở cấp độ từ vựng; xem cấu trúc cụm từ, dưới đây. Thứ hai, trong một số cách sử dụng từ vựng, các bình luận và khoảng trắng phải được giữ nguyên – ví dụ, một người vẽ đẹp cũng cần xuất ra các bình luận và một số công cụ gỡ lỗi có thể cung cấp thông báo cho lập trình viên hiển thị mã nguồn gốc. Trong những năm 1960, đáng chú ý là ALGOL, khoảng trắng và các bình luận đã bị loại bỏ như là một phần của giai đoạn tái thiết dòng (giai đoạn ban đầu của giao diện trình biên dịch), nhưng giai đoạn riêng biệt này đã bị loại bỏ và hiện tại chúng đã được xử lý bởi nhà từ vựng.

Tokenization [ chỉnh sửa ]

Tokenization là quá trình phân định và có thể phân loại các phần của một chuỗi các ký tự đầu vào. Các mã thông báo kết quả sau đó được chuyển sang một số hình thức xử lý khác. Quá trình có thể được coi là một nhiệm vụ phụ của phân tích cú pháp đầu vào.

(Lưu ý: Token hóa trong lĩnh vực bảo mật máy tính có một ý nghĩa khác.)

Ví dụ: trong chuỗi văn bản:

Con cáo nâu nhanh nhẹn nhảy qua con chó lười

chuỗi không được phân chia ngầm trên các không gian, như một người nói ngôn ngữ tự nhiên sẽ làm. Đầu vào thô, 43 ký tự, phải được phân tách rõ ràng thành 9 mã thông báo với một dấu phân cách không gian nhất định (nghĩa là khớp với chuỗi "" hoặc biểu thức chính quy / s {1} / ).

Các mã thông báo có thể được biểu diễn bằng XML,

    Con cáo     nhanh     màu nâu     con cáo     nhảy     trên     con chó lười biếng         Hoặc là một biểu hiện, 

  ( câu      ( từ   )      ( từ   nhanh )      [ ] màu nâu )       ( từ   cáo )      ( từ   nhảy )      ( )       ( từ   )      ( từ   lười biếng )      ( từ   ]))  

Khi một lớp mã thông báo đại diện cho nhiều hơn một từ vựng có thể, lexer thường lưu đủ thông tin để tái tạo từ vựng gốc, để nó có thể được sử dụng trong phân tích ngữ nghĩa. Trình phân tích cú pháp thường lấy thông tin này từ lexer và lưu nó trong cây cú pháp trừu tượng. Điều này là cần thiết để tránh mất thông tin trong trường hợp số và định danh.

Mã thông báo được xác định dựa trên các quy tắc cụ thể của từ vựng. Một số phương pháp được sử dụng để xác định mã thông báo bao gồm: biểu thức chính quy, chuỗi ký tự cụ thể được gọi là cờ, ký tự phân tách cụ thể được gọi là dấu phân cách và định nghĩa rõ ràng bằng từ điển. Các ký tự đặc biệt, bao gồm các ký tự dấu chấm câu, thường được sử dụng bởi các từ vựng để xác định mã thông báo vì sử dụng tự nhiên trong ngôn ngữ viết và lập trình.

Mã thông báo thường được phân loại theo nội dung ký tự hoặc theo ngữ cảnh trong luồng dữ liệu. Thể loại được xác định bởi các quy tắc của lexer. Các danh mục thường liên quan đến các yếu tố ngữ pháp của ngôn ngữ được sử dụng trong luồng dữ liệu. Ngôn ngữ lập trình thường phân loại mã thông báo dưới dạng định danh, toán tử, biểu tượng nhóm hoặc theo loại dữ liệu. Ngôn ngữ viết thường phân loại mã thông báo là danh từ, động từ, tính từ hoặc dấu câu. Các danh mục được sử dụng để xử lý hậu kỳ các mã thông báo bởi trình phân tích cú pháp hoặc bởi các chức năng khác trong chương trình.

Một bộ phân tích từ vựng thường không làm gì với sự kết hợp của các mã thông báo, một nhiệm vụ còn lại cho trình phân tích cú pháp. Ví dụ: một bộ phân tích từ vựng điển hình nhận ra dấu ngoặc đơn là mã thông báo, nhưng không có gì để đảm bảo rằng mỗi "(" được khớp với ")".

Khi một lexer cung cấp mã thông báo cho trình phân tích cú pháp, biểu diễn được sử dụng thường là một danh sách liệt kê các biểu diễn số. Ví dụ: "Mã định danh" được biểu thị bằng 0, "Toán tử gán" với 1, "Toán tử bổ sung" với 2, v.v.

Mã thông báo được định nghĩa thường bằng các biểu thức chính quy, được hiểu bởi một bộ tạo phân tích từ vựng như lex. Trình phân tích từ vựng (được tạo tự động bởi một công cụ như lex hoặc thủ công) đọc trong một dòng ký tự, xác định các từ vựng trong luồng và phân loại chúng thành các thẻ. Điều này được gọi là token hóa . Nếu lexer tìm thấy mã thông báo không hợp lệ, nó sẽ báo lỗi.

Theo dõi mã thông báo là phân tích cú pháp. Từ đó, dữ liệu được giải thích có thể được tải vào các cấu trúc dữ liệu để sử dụng chung, giải thích hoặc biên dịch.

Máy quét [ chỉnh sửa ]

Giai đoạn đầu tiên, máy quét thường dựa trên máy trạng thái hữu hạn (FSM). Nó đã được mã hóa trong thông tin về các chuỗi ký tự có thể có trong bất kỳ mã thông báo nào mà nó xử lý (các trường hợp riêng lẻ của các chuỗi ký tự này được gọi là từ vựng). Ví dụ: mã thông báo số nguyên có thể chứa bất kỳ chuỗi ký tự chữ số nào. Trong nhiều trường hợp, ký tự không phải khoảng trắng đầu tiên có thể được sử dụng để suy ra loại mã thông báo tiếp theo và các ký tự đầu vào tiếp theo sau đó được xử lý một lần cho đến khi đạt được một ký tự không có trong bộ ký tự được chấp nhận cho mã thông báo đó (điều này được gọi là munch tối đa hoặc trận đấu dài nhất quy tắc). Trong một số ngôn ngữ, quy tắc tạo từ vựng phức tạp hơn và có thể liên quan đến việc quay lại các ký tự đã đọc trước đó. Ví dụ: trong C, một ký tự 'L' là không đủ để phân biệt giữa một mã định danh bắt đầu bằng 'L' và một chuỗi ký tự rộng.

Trình đánh giá [ chỉnh sửa ]

Tuy nhiên, một từ vựng chỉ là một chuỗi các ký tự được biết là thuộc một loại nhất định (ví dụ: một chuỗi ký tự, một chuỗi các chữ cái). Để tạo mã thông báo, bộ phân tích từ vựng cần có giai đoạn thứ hai, bộ đánh giá đi qua các ký tự của từ vựng để tạo ra giá trị . Loại của lexeme kết hợp với giá trị của nó là những gì tạo thành mã thông báo chính xác, có thể được trao cho trình phân tích cú pháp. Một số mã thông báo như dấu ngoặc đơn không thực sự có giá trị và do đó, hàm đánh giá cho các giá trị này có thể không trả về gì: chỉ cần loại. Tương tự, đôi khi các nhà đánh giá có thể triệt tiêu hoàn toàn một từ vựng, che giấu nó khỏi trình phân tích cú pháp, rất hữu ích cho khoảng trắng và các bình luận. Các đánh giá cho mã định danh thường đơn giản (đại diện theo nghĩa đen của mã định danh), nhưng có thể bao gồm một số unstropping. Các bộ đánh giá cho các số nguyên có thể chuyển chuỗi trên (trì hoãn đánh giá cho giai đoạn phân tích ngữ nghĩa) hoặc có thể tự thực hiện đánh giá, có thể liên quan đến các cơ sở hoặc số dấu phẩy động khác nhau. Đối với một chuỗi ký tự được trích dẫn đơn giản, người đánh giá chỉ cần loại bỏ các dấu ngoặc kép, nhưng người đánh giá cho một chuỗi ký tự thoát được kết hợp với một từ vựng, không bỏ qua các chuỗi thoát.

Ví dụ, trong mã nguồn của chương trình máy tính, chuỗi

net_worth_future = ( tài sản - nợ phải trả );

; khoảng trắng bị chặn và các ký tự đặc biệt không có giá trị:

 IDENTIFIER net_worth_future THIẾT BỊ KHAI THÁC Tài sản IDENTIFIER DẤU TRỪ Nợ phải trả CLOSE_PARENTHESIS SEMICOLON 

Mặc dù có thể và đôi khi cần thiết, do hạn chế cấp phép của các trình phân tích cú pháp hiện có hoặc nếu danh sách mã thông báo nhỏ, để viết một từ vựng bằng tay, các từ vựng thường được tạo bởi các công cụ tự động. Các công cụ này thường chấp nhận các biểu thức chính quy mô tả các mã thông báo được phép trong luồng đầu vào. Mỗi biểu thức chính quy được liên kết với một quy tắc sản xuất trong ngữ pháp từ vựng của ngôn ngữ lập trình để đánh giá các từ vựng phù hợp với biểu thức chính quy. Các công cụ này có thể tạo mã nguồn có thể được biên dịch và thực thi hoặc xây dựng bảng chuyển trạng thái cho máy trạng thái hữu hạn (được cắm vào mã mẫu để biên dịch và thực thi).

Các biểu thức chính quy biểu thị gọn các mẫu mà các ký tự trong từ vựng có thể theo. Ví dụ: đối với ngôn ngữ dựa trên tiếng Anh, mã thông báo IDENTIFIER có thể là bất kỳ ký tự chữ cái tiếng Anh hoặc dấu gạch dưới, theo sau là bất kỳ số lượng các ký tự chữ và số ASCII và / hoặc dấu gạch dưới. Điều này có thể được biểu diễn ngắn gọn bằng chuỗi [a-zA-Z_][a-zA-Z_0-9] * . Điều này có nghĩa là "bất kỳ ký tự a-z, A-Z hoặc _, theo sau là 0 hoặc nhiều hơn a-z, A-Z, _ hoặc 0-9".

Các biểu thức chính quy và các máy trạng thái hữu hạn mà chúng tạo ra không đủ mạnh để xử lý các mẫu đệ quy, chẳng hạn như " n mở ngoặc đơn, theo sau là một câu lệnh, sau đó là n dấu ngoặc đơn. " Họ không thể tiếp tục đếm và xác minh rằng n giống nhau ở cả hai bên, trừ khi tồn tại một tập hợp hữu hạn các giá trị cho phép đối với n . Phải có một trình phân tích cú pháp đầy đủ để nhận ra các mẫu như vậy trong tổng quát đầy đủ của chúng. Một trình phân tích cú pháp có thể đẩy các dấu ngoặc đơn trên một ngăn xếp và sau đó thử bật chúng ra và xem liệu ngăn xếp đó có trống không ở cuối không (xem ví dụ [5] trong sách Cấu trúc và diễn giải các chương trình máy tính ).

Chướng ngại vật [ chỉnh sửa ]

Thông thường, mã thông báo xảy ra ở cấp độ từ. Tuy nhiên, đôi khi rất khó để định nghĩa "từ" nghĩa là gì. Thông thường, một mã thông báo dựa trên các heuristic đơn giản, ví dụ:

  • Dấu câu và khoảng trắng có thể có hoặc không có trong danh sách kết quả của mã thông báo.
  • Tất cả các chuỗi ký tự chữ cái liền kề là một phần của một mã thông báo; Tương tự như vậy với các số.
  • Mã thông báo được phân tách bằng các ký tự khoảng trắng, chẳng hạn như dấu cách hoặc dấu cách hoặc dấu chấm câu.

Trong các ngôn ngữ sử dụng khoảng trắng giữa các từ (chẳng hạn như hầu hết sử dụng bảng chữ cái Latinh và hầu hết ngôn ngữ lập trình), cách tiếp cận này khá đơn giản. Tuy nhiên, ngay cả ở đây có nhiều trường hợp cạnh như các cơn co thắt, các từ được gạch nối, biểu tượng cảm xúc và các cấu trúc lớn hơn như URI (đối với một số mục đích có thể được tính là các mã thông báo duy nhất). Một ví dụ kinh điển là "có trụ sở tại New York", một mã thông báo ngây thơ có thể bị phá vỡ tại không gian mặc dù sự phá vỡ tốt hơn (được cho là) ​​ở dấu gạch nối.

Token hóa đặc biệt khó khăn đối với các ngôn ngữ được viết bằng scriptio continua, không có ranh giới từ nào như tiếng Hy Lạp cổ đại, tiếng Trung Quốc, [6] hoặc tiếng Thái. Các ngôn ngữ kết tụ, như tiếng Hàn, cũng làm cho các tác vụ mã thông báo trở nên phức tạp.

Một số cách để giải quyết các vấn đề khó khăn hơn bao gồm phát triển các phương pháp phỏng đoán phức tạp hơn, truy vấn bảng các trường hợp đặc biệt phổ biến hoặc điều chỉnh mã thông báo cho mô hình ngôn ngữ xác định collocations trong bước xử lý sau.

Phần mềm [ chỉnh sửa ]

  • Apache OpenNLP bao gồm các mã thông báo dựa trên quy tắc và thống kê hỗ trợ nhiều ngôn ngữ
  • Ranh giới từ. Tiếng Anh cũng được hỗ trợ.
  • API mã thông báo văn bản HPE Haven OnDemand (Sản phẩm thương mại, có quyền truy cập freemium) sử dụng Mô hình khái niệm xác suất nâng cao để xác định trọng số mà thuật ngữ này giữ trong các chỉ mục văn bản được chỉ định
  • Công cụ Lex và trình biên dịch của nó được thiết kế để tạo mã cho các máy phân tích từ vựng nhanh dựa trên mô tả chính thức về cú pháp từ vựng. Nó thường được coi là không đủ cho các ứng dụng với một bộ quy tắc từ vựng phức tạp và các yêu cầu hiệu suất nghiêm trọng. Ví dụ: Bộ sưu tập trình biên dịch GNU (GCC) sử dụng các từ vựng viết tay.

Trình tạo bộ phát âm [ chỉnh sửa ]

Bộ tạo âm thường được tạo bởi bộ tạo từ khóa , tương tự với trình tạo phân tích cú pháp và các công cụ như vậy thường đi kèm với nhau. Thành lập nhiều nhất là lex, được ghép nối với trình tạo bộ phân tích cú pháp yacc và flex / bison tương đương miễn phí. Các trình tạo này là một dạng ngôn ngữ dành riêng cho miền, có một đặc tả từ vựng - nói chung là các biểu thức chính quy với một số đánh dấu - và phát ra một từ vựng.

Những công cụ này mang lại sự phát triển rất nhanh, điều này rất quan trọng trong sự phát triển ban đầu, cả để có được một từ vựng hoạt động và bởi vì một đặc tả ngôn ngữ có thể thay đổi thường xuyên. Hơn nữa, họ thường cung cấp các tính năng nâng cao, chẳng hạn như các điều kiện trước và sau khó lập trình bằng tay. Tuy nhiên, một từ vựng được tạo tự động có thể thiếu tính linh hoạt và do đó có thể yêu cầu một số sửa đổi thủ công hoặc một từ vựng được viết hoàn toàn thủ công.

Hiệu suất của Lexer là một mối quan tâm và tối ưu hóa là đáng giá, vì vậy, trong các ngôn ngữ ổn định nơi lexer được chạy rất thường xuyên (chẳng hạn như C hoặc HTML). lexers tạo ra lex / flex có tốc độ khá nhanh, nhưng có thể cải thiện hai đến ba lần bằng cách sử dụng các máy phát được điều chỉnh nhiều hơn. Các từ vựng viết tay đôi khi được sử dụng, nhưng các trình tạo từ vựng hiện đại tạo ra các từ vựng nhanh hơn so với hầu hết các từ khóa viết tay. Họ máy phát điện lex / flex sử dụng cách tiếp cận theo bảng mà hiệu quả thấp hơn nhiều so với cách tiếp cận được mã hóa trực tiếp. [ đáng ngờ ] Với cách tiếp cận sau tạo ra một động cơ trực tiếp nhảy đến các trạng thái tiếp theo thông qua các câu lệnh goto. Các công cụ như re2c [7] đã được chứng minh là tạo ra các động cơ nhanh hơn từ hai đến ba lần so với các động cơ được sản xuất flex. [ cần trích dẫn ] Nói chung rất khó để viết phân tích bằng tay hoạt động tốt hơn động cơ được tạo ra bởi các công cụ sau này. . của cổ điển lex cho C / C ++

  • Ragel - máy tạo trạng thái và trình tạo lexer với đầu ra trong C, C ++ và hội
  • re2c - trình tạo từ vựng cho C và C ++
  • máy phân tích có thể xử lý Unicode:

    • JavaCC - tạo các máy phân tích từ vựng được viết bằng Java
    • JFLex - trình tạo phân tích từ vựng cho Java
    • AnnoFlex - trình tạo mã dựa trên chú thích cho máy quét từ vựng cho Java
    • RE / flex đối với C ++, tạo các máy quét với các bảng hoặc mã trực tiếp
    • Trình tạo phân tích từ vựng phổ quát nhanh cho C và C ++ được viết bằng Python
    • Trình tạo FsLex - lexer cho đầu vào byte và ký tự Unicode cho F #
    • và C ++ [8]
    • PLY - mô-đun Python ply.lex cho phép phân tích từ vựng

    Cấu trúc cụm từ [ chỉnh sửa ]

    phân đoạn luồng đầu vào của các ký tự thành các mã thông báo, chỉ cần nhóm các ký tự thành các mảnh và phân loại chúng. Tuy nhiên, từ vựng có thể phức tạp hơn đáng kể; đơn giản nhất, các nhà ngoại giao có thể bỏ qua các mã thông báo hoặc chèn thêm các mã thông báo. Việc bỏ qua các mã thông báo, đáng chú ý là khoảng trắng và các bình luận, là rất phổ biến, khi các trình biên dịch không cần thiết. Ít phổ biến hơn, các mã thông báo được thêm vào có thể được chèn vào. Điều này được thực hiện chủ yếu để nhóm các mã thông báo thành các câu lệnh hoặc các câu lệnh thành các khối để đơn giản hóa trình phân tích cú pháp.

    Tiếp tục dòng [ chỉnh sửa ]

    Tiếp tục dòng là một tính năng của một số ngôn ngữ trong đó một dòng mới thường là dấu kết thúc câu lệnh. Thông thường, kết thúc một dòng có dấu gạch chéo ngược (ngay sau dòng mới) dẫn đến dòng là tiếp tục - dòng sau là đã nối với dòng trước. Điều này thường được thực hiện trong lexer: dấu gạch chéo ngược và dòng mới bị loại bỏ, thay vì dòng mới được mã hóa. Các ví dụ bao gồm bash, [9] các tập lệnh shell khác và Python. [10]

    Chèn dấu chấm phẩy [ chỉnh sửa ]

    Nhiều ngôn ngữ sử dụng dấu chấm phẩy làm dấu kết thúc câu lệnh. Thông thường, điều này là bắt buộc, nhưng trong một số ngôn ngữ, dấu chấm phẩy là tùy chọn trong nhiều ngữ cảnh. Điều này chủ yếu được thực hiện ở cấp độ lexer, trong đó lexer tạo ra dấu chấm phẩy vào luồng mã thông báo, mặc dù không có mặt trong luồng ký tự đầu vào và được gọi là dấu chấm phẩy tự động hoặc . Trong những trường hợp này, dấu chấm phẩy là một phần của ngữ pháp cụm từ chính thức của ngôn ngữ, nhưng có thể không được tìm thấy trong văn bản đầu vào, vì chúng có thể được chèn bởi từ vựng. Dấu chấm phẩy tùy chọn hoặc dấu chấm dứt hoặc dấu phân tách khác đôi khi cũng được xử lý ở cấp trình phân tích cú pháp, đáng chú ý là trong trường hợp dấu phẩy hoặc dấu chấm phẩy.

    Chèn dấu chấm phẩy là một tính năng của BCPL và hậu duệ xa xôi của nó, [11] mặc dù nó không có trong B hoặc C. [12] Chèn dấu chấm phẩy có trong JavaScript, mặc dù các quy tắc có phần phức tạp và bị chỉ trích nhiều; để tránh lỗi, một số khuyến nghị luôn luôn sử dụng dấu chấm phẩy, trong khi những người khác sử dụng dấu chấm phẩy ban đầu, được gọi là dấu chấm phẩy phòng thủ, khi bắt đầu các tuyên bố mơ hồ.

    Chèn dấu chấm phẩy (trong các ngôn ngữ có câu lệnh chấm dứt dấu chấm phẩy) và tiếp tục dòng (trong các ngôn ngữ có câu lệnh kết thúc dòng mới) có thể được xem là bổ sung: chèn dấu chấm phẩy thêm mã thông báo, mặc dù các dòng mới thường không tạo mã thông báo, trong khi việc tiếp tục dòng ngăn không cho mã thông báo được tạo, mặc dù các dòng mới nói chung làm tạo mã thông báo.

    Quy tắc bên ngoài [ chỉnh sửa ]

    Quy tắc bên ngoài (các khối được xác định bằng cách thụt lề) có thể được thực hiện trong lexer, như trong Python, trong đó tăng kết quả thụt lề trong lexer phát ra mã thông báo INDENT và giảm kết quả thụt lề trong lexer phát ra mã thông báo DEDENT. [10] Các mã thông báo này tương ứng với dấu ngoặc mở { và đóng dấu ngoặc kép } sử dụng dấu ngoặc nhọn cho các khối và có nghĩa là cụm từ ngữ pháp không phụ thuộc vào việc sử dụng dấu ngoặc hay thụt lề. Điều này đòi hỏi trạng thái giữ từ vựng, cụ thể là mức thụt lề hiện tại và do đó có thể phát hiện các thay đổi khi thụt lề khi thay đổi này và do đó ngữ pháp từ vựng không có ngữ cảnh: INDENTITH DEDENT phụ thuộc vào thông tin theo ngữ cảnh của cấp độ thụt lề trước.

    Từ vựng nhạy cảm theo ngữ cảnh [ chỉnh sửa ]

    Các ngữ pháp từ vựng nói chung là không có ngữ cảnh, hoặc gần như vậy, do đó không yêu cầu nhìn lại hoặc quay lại, hoặc quay lại, cho phép đơn giản , sạch sẽ, và thực hiện hiệu quả. Điều này cũng cho phép giao tiếp một chiều đơn giản từ lexer đến trình phân tích cú pháp, mà không cần bất kỳ thông tin nào chảy ngược lại từ lexer.

    Tuy nhiên, có những ngoại lệ. Các ví dụ đơn giản bao gồm: chèn dấu chấm phẩy trong Go, yêu cầu nhìn lại một mã thông báo; nối các chuỗi ký tự chuỗi liên tiếp trong Python, [10] yêu cầu giữ một mã thông báo trong bộ đệm trước khi phát ra nó (để xem mã thông báo tiếp theo có phải là một chuỗi ký tự khác không); và quy tắc phụ trong Python, yêu cầu duy trì số lượng mức thụt lề (thực sự là một ngăn xếp của mỗi cấp độ thụt lề). Tất cả các ví dụ này chỉ yêu cầu bối cảnh từ vựng, và trong khi chúng làm phức tạp một phần từ vựng, chúng vô hình đối với trình phân tích cú pháp và các giai đoạn sau.

    Một ví dụ phức tạp hơn là hack lexer trong C, trong đó lớp mã thông báo của một chuỗi các ký tự không thể được xác định cho đến giai đoạn phân tích ngữ nghĩa, vì tên typedef và tên biến giống nhau về mặt từ vựng nhưng tạo thành các lớp mã thông báo khác nhau. Do đó, trong bản hack, lexer gọi bộ phân tích ngữ nghĩa (giả sử, bảng ký hiệu) và kiểm tra xem chuỗi có yêu cầu tên typedef hay không. Trong trường hợp này, thông tin phải chảy ngược lại không chỉ từ trình phân tích cú pháp, mà từ bộ phân tích ngữ nghĩa trở lại từ vựng, làm phức tạp thiết kế.

    Tài liệu tham khảo [ chỉnh sửa ]

    1. ^ "Giải phẫu trình biên dịch và mã thông báo". www.cs.man.ac.uk .
    2. ^ a b trang 111, "Nguyên tắc biên dịch, Kỹ thuật, & Công cụ, Ed lần thứ 2. " (WorldCat) của Aho, Lam, Sethi và Ullman, như được trích dẫn trong https://stackoverflow.com/questions/14954721/what-is-the-difference-b Among-token-and-lexeme[19659223[[[19659218[5ngườikhuânvác"Tàiliệuperlinterp:Perl5phiênbản240" perldoc.perl.org - Tài liệu chính thức cho ngôn ngữ lập trình Perl . perldoc.perl.org . Truy cập 26 tháng 1 2017 .
    3. ^ Guy Coder (19 tháng 2 năm 2013). "Sự khác biệt giữa mã thông báo và lexeme là gì?". Tràn ngăn xếp . Trao đổi ngăn xếp Inc . Truy cập 26 tháng 1 2017 .
    4. ^ "Cấu trúc và giải thích các chương trình máy tính". mitpress.mit.edu .
    5. ^ Huang, C., Simon, P., Hsieh, S., & Prevot, L. (2007) Suy nghĩ lại về phân đoạn từ tiếng Trung: Tokenization, Ký tự Phân loại, hoặc Nhận dạng ngắt từ
    6. ^ Bumbulis, P.; Cowan, D. D. (Mar 12 tháng 12 năm 1993). "RE2C: Một máy phát quét đa năng hơn". Chữ cái ACM về ngôn ngữ lập trình và hệ thống . 2 (1 Vé4): 70 Bóng84. doi: 10.1145 / 176454.176487.
    7. ^ [1]hướng dẫn re2c
    8. ^ Tài liệu tham khảo Bash 3.1.2.1 Ký tự thoát
    9. b c "Tài liệu 3.6.4". docs.python.org .
    10. ^ Đi hiệu quả "Dấu chấm phẩy"
    11. ^ "Dấu chấm phẩy trong Go", golang-nut, Rob ' Chỉ huy 'Pike, 12/10/09

    Nguồn [ chỉnh sửa ]

    • Biên dịch với C # và Java Pat Terry, 2005, ISBN 032126360X
    • Thuật toán + Cấu trúc dữ liệu = Chương trình Niklaus Wirth, 1975, ISBN 0-13-022418-9
    • Xây dựng trình biên dịch Niklaus Wirth, 1996, [194591110-201-40353-6
    • Sebesta, RW (2006). Các khái niệm về ngôn ngữ lập trình (ấn bản thứ bảy) trang 177. Boston: Pearson / Addison-Wesley.

    Liên kết ngoài [ chỉnh sửa ]