chân - Trực tuyến trên đám mây

CHƯƠNG TRÌNH:

TÊN

peg, leg - trình phân tích cú pháp

SYNOPSIS

peg [-hvV -đầu ra] [tên tệp ...]
Chân [-hvV -đầu ra] [tên tệp ...]

MÔ TẢ

peg và Chân là các công cụ để tạo trình phân tích cú pháp gốc đệ quy: các chương trình thực hiện
khớp mẫu trên văn bản. Họ xử lý Ngữ pháp diễn đạt phân tích cú pháp (PEG) [Ford 2004] để
tạo ra một chương trình nhận dạng các câu hợp pháp của ngữ pháp đó. peg xử lý PEG
được viết bằng cú pháp gốc được Ford mô tả; Chân xử lý PEG được viết bằng cách sử dụng
cú pháp và quy ước hơi khác nhằm mục đích làm cho nó trở nên hấp dẫn
thay thế cho trình phân tích cú pháp được xây dựng bằng lex(1) yac(1). không giống lex và yac, peg và Chân
hỗ trợ backtracking không giới hạn, cung cấp lựa chọn theo thứ tự như một phương tiện để định hướng và
có thể kết hợp quét (phân tích từ vựng) và phân tích cú pháp (phân tích cú pháp) thành một
Hoạt động.

peg đọc các chỉ định tên tập tins, hoặc đầu vào tiêu chuẩn nếu không tên tập tins được đưa ra, cho một
ngữ pháp mô tả trình phân tích cú pháp để tạo. peg sau đó tạo một tệp nguồn C
xác định một chức năng yyparse (). Tệp nguồn C này có thể được đưa vào hoặc được biên dịch và sau đó
được liên kết với, một chương trình khách hàng. Mỗi khi chương trình khách hàng gọi yyparse() trình phân tích cú pháp
sử dụng văn bản đầu vào theo quy tắc phân tích cú pháp, bắt đầu từ quy tắc đầu tiên trong
ngữ pháp. yyparse() trả về khác XNUMX nếu đầu vào có thể được phân tích cú pháp theo
ngữ pháp; nó trả về XNUMX nếu không thể phân tích cú pháp đầu vào.

Tiền tố 'yy' hoặc 'YY' được thêm vào trước tất cả các ký hiệu có thể nhìn thấy bên ngoài trong
trình phân tích cú pháp. Điều này nhằm giảm nguy cơ ô nhiễm không gian tên trong các chương trình máy khách.
(Lựa chọn 'yy' là lịch sử; xem lex(1) yac(1) chẳng hạn.)

LỰA CHỌN

peg và Chân cung cấp các tùy chọn sau:

-h in một bản tóm tắt các tùy chọn có sẵn và sau đó thoát ra.

-đầu ra
ghi trình phân tích cú pháp đã tạo vào tệp đầu ra thay vì đầu ra tiêu chuẩn.

-v ghi thông tin dài dòng vào lỗi chuẩn trong khi làm việc.

-V ghi thông tin phiên bản vào lỗi chuẩn rồi thoát.

A ĐƠN GIẢN THÍ DỤ

Sau đây peg đầu vào chỉ định một ngữ pháp với một quy tắc duy nhất (được gọi là 'bắt đầu') là
hài lòng khi đầu vào chứa chuỗi "tên người dùng".

bắt đầu <- "tên người dùng"

(Dấu ngoặc kép là không một phần của văn bản phù hợp; chúng dùng để chỉ một nghĩa đen
chuỗi được so khớp.) Nói cách khác, yyparse() trong nguồn C được tạo sẽ trả về
khác XNUMX chỉ khi tám ký tự tiếp theo đọc từ đầu vào đánh vần từ "tên người dùng".
Nếu đầu vào chứa bất kỳ thứ gì khác, yyparse() trả về XNUMX và không có đầu vào nào
đã tiêu thụ. (Các cuộc gọi tiếp theo tới yyparse() cũng sẽ trả về XNUMX, vì trình phân tích cú pháp là
bị chặn hiệu quả khi tìm kiếm chuỗi "tên người dùng".) Để đảm bảo tiến độ, chúng tôi có thể thêm một
mệnh đề thay thế cho quy tắc 'bắt đầu' sẽ khớp với bất kỳ ký tự đơn nào nếu là "tên người dùng"
không được tìm thấy.

bắt đầu <- "tên người dùng"
/.

yyparse() bây giờ luôn trả về khác XNUMX (ngoại trừ ở cuối đầu vào). Làm
một cái gì đó hữu ích, chúng tôi có thể thêm các hành động vào các quy tắc. Những hành động này được thực hiện sau khi
kết hợp hoàn chỉnh được tìm thấy (bắt đầu từ quy tắc đầu tiên) và được chọn theo
'đường dẫn' thông qua ngữ pháp để khớp với đầu vào. (Các nhà ngôn ngữ học gọi con đường này là
'điểm đánh dấu cụm từ'.)

start <- "tên người dùng" {printf ("% s \ n", getlogin ()); }
/ <. > {putchar (yytext [0]); }

Dòng đầu tiên hướng dẫn trình phân tích cú pháp in tên đăng nhập của người dùng bất cứ khi nào nó nhìn thấy
"tên người dùng" trong đầu vào. Nếu kết hợp đó không thành công, dòng thứ hai yêu cầu trình phân tích cú pháp lặp lại
ký tự tiếp theo trên đầu vào đầu ra tiêu chuẩn. Trình phân tích cú pháp của chúng tôi hiện đang hoạt động hữu ích
công việc: nó sẽ sao chép đầu vào thành đầu ra, thay thế tất cả các lần xuất hiện của "tên người dùng" bằng
tên tài khoản của người dùng.

Lưu ý các dấu ngoặc nhọn ('<' và '>') đã được thêm vào phương án thứ hai. Này
không ảnh hưởng đến ý nghĩa của quy tắc, nhưng dùng để phân tách văn bản được cung cấp cho
hành động sau trong biến văn bản yy.

Nếu ngữ pháp trên được đặt trong tệp tên người dùng.peg, chạy lệnh

chốt -o tên người dùng.c tên người dùng.peg

sẽ lưu trình phân tích cú pháp tương ứng trong tệp tên người dùng.c. Để tạo một chương trình hoàn chỉnh
trình phân tích cú pháp này có thể được đưa vào bởi một chương trình C như sau.

#bao gồm / * printf (), putchar () * /
#bao gồm / * getlogin () * /

#include "username.c" / * yyparse () * /

int main ()
{
while (yyparse ()) / * lặp lại cho đến khi EOF * /
;
0 trở về;
}

PEG NGỮ PHÁP

Một ngữ pháp bao gồm một tập hợp các quy tắc được đặt tên.

tên <- mẫu

Belt Hold chứa một hoặc nhiều phần tử sau.

tên Phần tử là viết tắt của toàn bộ mẫu trong quy tắc với tên.

"nhân vật"
Một ký tự hoặc chuỗi được đặt trong dấu ngoặc kép được so khớp theo nghĩa đen. ANSI C
trình tự thoát được công nhận trong nhân vật.

'nhân vật'
Một ký tự hoặc chuỗi được đặt trong dấu ngoặc kép được so khớp theo nghĩa đen, như trên.

[nhân vật]
Một tập hợp các ký tự được đặt trong dấu ngoặc vuông khớp với bất kỳ ký tự đơn nào từ
bộ, với các ký tự thoát được nhận dạng như trên. Nếu tập hợp bắt đầu bằng
uparrow (^) thì tập hợp bị phủ định (phần tử khớp với bất kỳ ký tự nào không trong
bộ). Bất kỳ cặp ký tự nào được phân tách bằng dấu gạch ngang (-) đại diện cho phạm vi
ký tự từ ký tự đầu tiên đến ký tự thứ hai, bao gồm. Một ký tự chữ cái duy nhất
hoặc dấu gạch dưới được khớp bởi tập hợp sau.

[a-zA-Z_]

Tương tự, phần sau phù hợp với bất kỳ ký tự không phải chữ số nào.

[^ 0-9]

. Một dấu chấm phù hợp với bất kỳ ký tự nào. Lưu ý rằng lần duy nhất điều này không thành công là vào cuối
tệp, nơi không có ký tự nào để khớp.

( Belt Hold )
Dấu ngoặc đơn được sử dụng để nhóm (sửa đổi mức độ ưu tiên của các toán tử
được mô tả dưới đây).

{ hoạt động }
Các dấu ngoặc nhọn bao quanh các hành động. Hành động là mã nguồn C tùy ý để được
được thực hiện khi kết thúc khớp lệnh. Bất kỳ dấu ngoặc nhọn nào trong hành động phải đúng
lồng vào nhau. Bất kỳ văn bản đầu vào nào được khớp trước hành động và được phân tách theo góc
dấu ngoặc (xem bên dưới) được tạo sẵn trong action vì nội dung của
mảng ký tự văn bản yy. Độ dài của (số ký tự trong) văn bản yy is
có sẵn trong biến yylen. (Những tên biến này là lịch sử; xem
lex(1).)

< Dấu ngoặc nhọn mở luôn khớp (không sử dụng đầu vào) và gây ra trình phân tích cú pháp
để bắt đầu tích lũy văn bản phù hợp. Văn bản này sẽ được cung cấp cho các hành động trong
biến văn bản yy.

> Dấu ngoặc nhọn đóng luôn khớp (không sử dụng đầu vào) và khiến trình phân tích cú pháp
ngừng tích lũy văn bản cho văn bản yy.

Trên đây thành phầns có thể là tùy chọn và / hoặc có thể lặp lại với các hậu tố sau:

thành phần ?
Phần tử là tùy chọn. Nếu xuất hiện trên đầu vào, nó được tiêu thụ và khớp
thành công. Nếu không có trên đầu vào, không có văn bản nào được sử dụng và trận đấu thành công
dù sao.

thành phần +
Phần tử có thể lặp lại. Nếu xuất hiện trên đầu vào, một hoặc nhiều lần xuất hiện
thành phần được tiêu thụ và trận đấu thành công. Nếu không có sự xuất hiện của thành phần đang
hiện trên đầu vào, trận đấu không thành công.

thành phần *
Phần tử là tùy chọn và có thể lặp lại. Nếu có trên đầu vào, một hoặc nhiều
sự xuất hiện của thành phần được tiêu thụ và trận đấu thành công. Nếu không có sự xuất hiện của
thành phần có mặt trên đầu vào, trận đấu vẫn thành công.

Các phần tử và hậu tố ở trên có thể được chuyển đổi thành các vị từ (phù hợp tùy ý
nhập văn bản và sau đó thành công hay thất bại không có sử dụng đầu vào đó) với
các tiền tố sau:

& thành phần
Vị ngữ chỉ thành công khi thành phần có thể được kết hợp. Nhập văn bản được quét trong khi
phù hợp thành phần không được sử dụng từ đầu vào và vẫn có sẵn cho
kết hợp tiếp theo.

! thành phần
Vị ngữ chỉ thành công khi thành phần không thể đối sánh. Nhập văn bản được quét trong khi
phù hợp thành phần không được sử dụng từ đầu vào và vẫn có sẵn cho
kết hợp tiếp theo. Một thành ngữ phổ biến là

!.

khớp với phần cuối của tệp, sau khi ký tự cuối cùng của đầu vào đã
đã được tiêu thụ.

Một dạng đặc biệt của vị từ '&' được cung cấp:

&{ biểu hiện }
Trong vị ngữ này, C đơn giản biểu hiện (không tuyên bố) được đánh giá ngay lập tức
khi trình phân tích cú pháp đến vị ngữ. Nếu biểu hiện cho kết quả khác XNUMX (true)
'so khớp' thành công và trình phân tích cú pháp tiếp tục với phần tử tiếp theo trong mẫu.
Nếu biểu hiện cho kết quả bằng không (sai), 'so khớp' không thành công và trình phân tích cú pháp sao lưu vào
tìm kiếm một phân tích cú pháp thay thế của đầu vào.

Một số phần tử (có hoặc không có tiền tố và hậu tố) có thể được kết hợp thành một trình tự
bằng cách viết chúng lần lượt. Toàn bộ chuỗi chỉ khớp nếu mỗi cá nhân
phần tử bên trong nó khớp, từ trái sang phải.

Các chuỗi có thể được phân tách thành các lựa chọn thay thế riêng biệt bằng toán tử thay thế '/'.

trình tự-1 / trình tự-2 / ... / trình tự-N
Lần lượt từng chuỗi được thử cho đến khi một trong số chúng khớp, lúc đó khớp
cho mô hình tổng thể thành công. Nếu không có trình tự nào khớp thì khớp
của mô hình tổng thể không thành công.

Cuối cùng, dấu thăng (#) giới thiệu một nhận xét (bị loại bỏ) tiếp tục cho đến khi kết thúc
của dòng.

Để tóm tắt ở trên, trình phân tích cú pháp cố gắng đối sánh văn bản đầu vào với một mẫu
chứa các ký tự, tên (đại diện cho các quy tắc khác) và các toán tử khác nhau (được viết dưới dạng
tiền tố, hậu tố, vị trí liền kề để sắp xếp trình tự và và toán tử thay thế tiền tố) mà
sửa đổi cách khớp các phần tử trong mẫu. Các trận đấu được thực hiện từ trái sang
phải, 'giảm dần' vào các quy tắc phụ được đặt tên khi chúng gặp phải. Nếu quá trình khớp
không thành công, trình phân tích cú pháp 'quay lại theo dõi' ('tua lại' đầu vào một cách thích hợp trong quá trình này) để
tìm 'đường dẫn' thay thế gần nhất thông qua ngữ pháp. Nói cách khác, trình phân tích cú pháp
thực hiện tìm kiếm theo chiều sâu, từ trái sang phải cho đường dẫn khớp thành công đầu tiên
thông qua các quy tắc. Nếu được tìm thấy, các hành động dọc theo đường dẫn thành công sẽ được thực thi (trong
thứ tự mà họ đã gặp phải).

Lưu ý rằng các vị từ được đánh giá ngay trong quá trình tìm kiếm một kết quả phù hợp thành công,
vì chúng góp phần vào sự thành công hay thất bại của việc tìm kiếm. Các hành động, tuy nhiên, là
chỉ đánh giá sau khi một trận đấu thành công đã được tìm thấy.

PEG NGỮ PHÁP CHO PEG NGỮ PHÁP

Ngữ pháp cho peg ngữ pháp được hiển thị bên dưới. Điều này sẽ minh họa và chính thức hóa
mô tả trên.

Ngữ pháp <- Định nghĩa khoảng cách + EndOfFile

Định nghĩa <- Biểu thức LEFTARROW Định danh
Biểu thức <- Trình tự (Trình tự SLASH) *
Trình tự <- Tiền tố *
Tiền tố <- AND Action
/ (VÀ | KHÔNG)? Hậu tố
Hậu tố <- Chính (QUERY / STAR / PLUS)?
Chính <- Định danh! LEFTARROW
/ MỞ biểu thức ĐÓNG
/ Nghĩa đen
/ Lớp
/ CHẤM
/ Hoạt động
/ BẮT ĐẦU
/ KẾT THÚC

Định danh <- <IdentStart IdentCont *> Khoảng cách
IdentStart <- [a-zA-Z_]
IdentCont <- IdentStart / [0-9]
Chữ nghĩa <- ['] <(! ['] Char) *> ['] Khoảng cách
/ ["] <(! ["] Char) *> ["] Khoảng cách
Lớp <- '[' <(! ']' Phạm vi) *> ']' Khoảng cách
Phạm vi <- Char '-' Char / Char
Biểu đồ <- '\\' [abefnrtv '"\ [\] \\]
/ '\\' [0-3][0-7][0-7]
/ '\\' [0-7] [0-7]?
/ '\\' '-'
/! '\\'.
LEFTARROW <- '<-' Khoảng cách
SLASH <- '/' Khoảng cách
VÀ Khoảng cách <- '&'
KHÔNG PHẢI <- '!' khoảng cách
QUERY <- '?' khoảng cách
STAR <- '*' Khoảng cách
CỘNG Khoảng cách <- '+'
MỞ <- '(' Khoảng cách
ĐÓNG <- ')' Khoảng cách
CHẤM <- '.' khoảng cách
Khoảng cách <- (Dấu cách / Nhận xét) *
Nhận xét <- '#' (! EndOfLine.) * EndOfLine
Dấu cách <- '' / '\ t' / EndOfLine
EndOfLine <- '\ r \ n' / '\ n' / '\ r'
EndOfFile <-!.
Hành động <- '{' <[^}] *> '}' Khoảng cách
BEGIN <- '<' Khoảng cách
HẾT <- '>' Khoảng cách

CHÂN NGỮ PHÁP

Chân là một biến thể của peg điều đó bổ sung một số tính năng của lex(1) yac(1). Nó khác với
peg bằng những cách sau đây.

%{ chữ... %}
Phần khai báo có thể xuất hiện ở bất kỳ đâu mà định nghĩa quy tắc được mong đợi. Các
văn bản giữa các dấu phân cách '% {' và '%}' được sao chép nguyên văn vào C được tạo
mã phân tích cú pháp trước mã thực hiện chính trình phân tích cú pháp.

tên = Belt Hold
Toán tử 'gán' thay thế toán tử mũi tên trái '<-'.

tên quy tắc
Dấu gạch nối có thể xuất hiện dưới dạng chữ cái trong tên của các quy tắc. Mỗi dấu gạch nối được chuyển đổi thành
dấu gạch dưới trong mã nguồn C được tạo. Một dấu gạch ngang duy nhất '-' là một
tên quy tắc pháp lý.

- = [\ t \ n \ r] *
số = [0-9] + -
tên = [a-zA-Z _] [a-zA_Z_0-9] * -
l-paren = '(' -
r-paren = ')' -

Ví dụ này cho thấy khoảng trắng bị bỏ qua có thể rõ ràng như thế nào khi đọc ngữ pháp
và không phô trương khi được đặt một cách tự do ở cuối mọi quy tắc liên quan đến
một yếu tố từ vựng.

phần tiếp theo 1 | phần tiếp theo 2
Toán tử thay thế là thanh dọc '|' chứ không phải là dấu gạch chéo '/'. Các
peg loại trừ

tên <- dãy-1
/ sequin-2
/ sequin-3

do đó được viết

tên = dãy-1
| dãy-2
| dãy-3
;

in Chân (với dấu chấm phẩy cuối cùng là tùy chọn, như được mô tả tiếp theo).

exp ~ { hoạt động }
Một toán tử postfix ~{ hoạt động } có thể được đặt sau bất kỳ biểu thức nào và sẽ hoạt động
giống như một hành động bình thường (mã C tùy ý) ngoại trừ việc nó chỉ được gọi khi exp
không thành công. Nó liên kết ít chặt chẽ hơn bất kỳ toán tử nào khác ngoại trừ sự thay thế và
giải trình tự và nhằm mục đích làm cho việc xử lý lỗi và mã khôi phục dễ dàng hơn
viết. Lưu ý rằng văn bản yy và yylen không có sẵn bên trong các hành động này, nhưng
biến con trỏ yy có sẵn để cung cấp quyền truy cập mã cho bất kỳ người dùng nào do người dùng xác định
thành viên của trạng thái phân tích cú pháp (xem "TÙY CHỈNH BỘ PHẬN" bên dưới). Cũng lưu ý rằng
exp luôn luôn là một biểu thức duy nhất; để gọi một hành động lỗi cho bất kỳ lỗi nào trong
một trình tự, dấu ngoặc đơn phải được sử dụng để nhóm trình tự thành một
biểu hiện.

rule = e1 e2 e3 ~ {error ("e [12] ok; e3 has failed"); }
| ...

rule = (e1 e2 e3) ~ {error ("một trong các e [123] bị lỗi"); }
| ...

Belt Hold ;
Dấu chấm câu chấm phẩy có thể tùy ý kết thúc một Belt Hold.

%% chữ...
Phần trăm kép '%%' chấm dứt phần quy tắc (và khai báo) của
ngữ pháp. Tất cả các văn bản sau '%%' được sao chép nguyên văn sang mã phân tích cú pháp C đã tạo
sau khi mã triển khai trình phân tích cú pháp.

$$ = giá trị
Một quy tắc phụ có thể trả về một ngữ nghĩa giá trị từ một hành động bằng cách gán nó cho
biến giả '$$'. Tất cả các giá trị ngữ nghĩa phải có cùng một loại (mặc định
thành 'int'). Loại này có thể được thay đổi bằng cách xác định YYSTYPE trong phần khai báo.

định danh:tên
Giá trị ngữ nghĩa được trả về (bằng cách gán cho '$$') từ quy tắc phụ tên is
Liên quan đến định danh và có thể được tham chiếu trong các hành động tiếp theo.

Ví dụ về máy tính bàn bên dưới minh họa việc sử dụng '$$' và ':'.

CHÂN THÍ DỤ: A BÀN MÁY TÍNH

Các phần mở rộng trong Chân được mô tả ở trên cho phép các trình phân tích cú pháp và đánh giá hữu ích (bao gồm
khai báo, quy tắc ngữ pháp và các hàm C hỗ trợ như 'main') được lưu giữ bên trong
một tệp nguồn duy nhất. Để minh họa điều này, chúng tôi hiển thị một máy tính bàn đơn giản hỗ trợ
bốn toán tử số học phổ biến và các biến được đặt tên. Các kết quả trung gian của
đánh giá số học sẽ được tích lũy trên một ngăn xếp ngầm bằng cách trả về chúng dưới dạng
giá trị ngữ nghĩa từ các quy tắc con.

%{
#bao gồm / * printf () * /
#bao gồm / * atoi () * /
int vars [26];
%}

Stmt = - e: Expr EOL {printf ("% d \ n", e); }
| (! EOL.) * EOL {printf ("error \ n"); }

Expr = i: ID ASSIGN s: Sum {$$ = vars [i] = s; }
| s: Tính tổng {$$ = s; }

Sum = l: Sản phẩm
(CỘNG R: Sản phẩm {l + = r;}
| TRỪ r: Tích {l - = r; }
) * {$$ = l; }

Sản phẩm = l: Giá trị
(TIMES r: Giá trị {l * = r;}
| CHIA r: Giá trị {l / = r; }
) * {$$ = l; }

Giá trị = i: NUMBER {$$ = atoi (yytext); }
| i: ID! ASSIGN {$$ = vars [i]; }
| MỞ i: Expr CLOSE {$$ = i; }

NUMBER = <[0-9] +> - {$$ = atoi (yytext); }
ID = <[az]> - {$$ = yytext [0] - 'a'; }
ASSIGN = '=' -
CỘNG = '+' -
TRỪ = '-' -
TIMES = '*' -
DIVIDE = '/' -
MỞ = '(' -
ĐÓNG = ')' -

- = [\ t] *
EOL = '\ n' | '\ r \ n' | '\ r' | ';'

%%

int main ()
{
trong khi (yyparse ())
;
0 trở về;
}

CHÂN NGỮ PHÁP CHO CHÂN NGỮ PHÁP

Ngữ pháp cho Chân ngữ pháp được hiển thị bên dưới. Điều này sẽ minh họa và chính thức hóa
mô tả trên.

ngữ pháp = -
(khai báo | định nghĩa) +
đoạn phim giới thiệu? phần cuối của tập tin

khai báo = '% {' <(! '%}'.) *> RPERCENT

trailer = '%%' <. *>

định nghĩa = định danh biểu thức EQUAL SEMICOLON?

biểu thức = chuỗi (chuỗi BAR) *

trình tự = lỗi +

error = prefix (hành động TILDE)?

tiền tố = hành động AND
| (VÀ | KHÔNG)? hậu tố

hậu tố = chính (QUERY | STAR | PLUS)?

chính = số nhận dạng Mã định danh COLON! EQUAL
| định danh! EQUAL
| MỞ biểu thức ĐÓNG
| theo nghĩa đen
| lớp
| CHẤM
| hoạt động
| BẮT ĐẦU
| KẾT THÚC

số nhận dạng = <[-a-zA-Z _] [- a-zA-Z_0-9] *> -

nghĩa đen = ['] <(! ['] char) *> ['] -
| ["] <(! ["] char) *> ["] -

class = '[' <(! ']' range) *> ']' -

range = char '-' char | char

char = '\\' [abefnrtv '"\ [\] \\]
| '\\' [0-3][0-7][0-7]
| '\\' [0-7] [0-7]?
| ! '\\'.

action = '{' <dấu ngoặc nhọn *> '}' -

niềng răng = '{' niềng răng * '}'
| ! '}'.

EQUAL = '=' -
COLON = ':' -
SEMICOLON = ';' -
BAR = '|' -
VÀ = '&' -
KHÔNG = '!' -
QUERY = '?' -
SAO = '*' -
CỘNG = '+' -
MỞ = '(' -
ĐÓNG = ')' -
DOT = '.' -
BEGIN = '<' -
HẾT = '>' -
TILDE = '~' -
RPERCENT = '%}' -

- = (dấu cách | bình luận) *
dấu cách = '' | '\ t' | kết thúc dòng
comment = '#' (! end-of-line.) * end-of-line
end-of-line = '\ r \ n' | '\ n' | '\NS'
end-of-file =!.

TÙY CHỈNH CÁC BỘ PHẬN

Các ký hiệu sau có thể được định nghĩa lại trong các phần khai báo để sửa đổi
mã phân tích cú pháp.

YYSLOẠI
Loại giá trị ngữ nghĩa. Biến giả '$$' và số nhận dạng 'bị ràng buộc' với
tất cả các kết quả quy tắc với toán tử dấu hai chấm ':' phải được coi là đã được khai báo
để có loại này. Giá trị mặc định là 'int'.

YYPARSE
Tên của điểm nhập chính vào trình phân tích cú pháp. Giá trị mặc định là 'yyparse'.

YYPARSEFROM
Tên của một điểm nhập thay thế cho trình phân tích cú pháp. Hàm này mong đợi một
đối số: hàm tương ứng với quy tắc mà từ đó tìm kiếm kết quả phù hợp
nên bắt đầu. Giá trị mặc định là 'yyparsefrom'. Lưu ý rằng yyparse () được định nghĩa là

int yyparse () {return yyparsefrom (yy_foo); }

trong đó 'foo' là tên của quy tắc đầu tiên trong ngữ pháp.

YY_INPUT (buf, kết quả, kích thước tối đa)
Macro này được trình phân tích cú pháp gọi ra để lấy thêm văn bản đầu vào. buf chỉ vào một
vùng bộ nhớ có thể chứa nhiều nhất kích thước tối đa nhân vật. Macro nên sao chép
nhập văn bản vào buf và sau đó gán biến số nguyên kết quả để chỉ ra
số ký tự được sao chép. Nếu không còn đầu vào nữa, macro sẽ
gán 0 cho kết quả. Theo mặc định, macro YY_INPUT được định nghĩa như sau.

#define YY_INPUT (buf, kết quả, max_size)
{
int yyc = getchar ();
kết quả = (EOF == yyc)? 0: (* (buf) = yyc, 1);
}

Lưu ý rằng nếu YY_CTX_LOCAL được xác định (xem bên dưới) thì đối số đầu tiên bổ sung,
chứa ngữ cảnh phân tích cú pháp, được chuyển tới YY_INPUT.

YY_DEBUG
Nếu ký hiệu này được xác định thì mã bổ sung sẽ được bao gồm trong trình phân tích cú pháp
in một lượng lớn thông tin phức tạp đến lỗi tiêu chuẩn trong khi trình phân tích cú pháp
đang chạy.

YY_BEGIN
Macro này được gọi để đánh dấu phần bắt đầu của văn bản đầu vào sẽ được cung cấp
trong các hành động dưới dạng 'yytext'. Điều này tương ứng với sự xuất hiện của '<' trong ngữ pháp.
Chúng được chuyển đổi thành các vị từ được mong đợi sẽ thành công. Mặc định
định nghĩa

#define YY_BEGIN (yybegin = yypos, 1)

do đó lưu vị trí đầu vào hiện tại và trả về 1 ('true') là kết quả của
vị ngữ.

YY_END Macro này tương ứng với '>' trong ngữ pháp. Một lần nữa, nó là một vị ngữ nên
định nghĩa mặc định lưu vị trí đầu vào trước khi 'thành công'.

#define YY_END (yyend = yypos, 1)

YY_PARSE (T)
Macro này khai báo các điểm nhập phân tích cú pháp (yyparse và yyparsefrom) thuộc loại
T. Định nghĩa mặc định

#define YY_PARSE (T) T

để lại yyparse () và yyparsefrom () với khả năng hiển thị toàn cầu. Nếu họ không nên
hiển thị bên ngoài trong các tệp nguồn khác, macro này có thể được xác định lại để khai báo
chúng 'tĩnh'.

#define YY_PARSE (T) tĩnh T

YY_CTX_LOCAL
Nếu ký hiệu này được xác định trong quá trình biên dịch bộ phân tích cú pháp đã tạo thì toàn cục
trạng thái phân tích cú pháp sẽ được giữ trong cấu trúc kiểu 'yycontext' có thể được khai báo
như một biến cục bộ. Điều này cho phép nhiều trường hợp phân tích cú pháp cùng tồn tại và
an toàn theo chủ đề. Hàm phân tích cú pháp yyparse() sẽ được khai báo để mong đợi một
đối số kiểu 'yycontext *', một ví dụ của cấu trúc chứa toàn cục
trạng thái cho trình phân tích cú pháp. Phiên bản này phải được cấp phát và khởi tạo bằng XNUMX bởi
khách hàng. Một ví dụ nhỏ nhưng đầy đủ là như sau.

#bao gồm

#xác định YY_CTX_LOCAL

#include "the-created-parser.peg.c"

int main ()
{
yycontext ctx;
memset (& ctx, 0, sizeof (yycontext));
while (yyparse (& ctx));
0 trở về;
}

Lưu ý rằng nếu ký hiệu này không được xác định thì trình phân tích cú pháp đã biên dịch sẽ tĩnh
phân bổ trạng thái toàn cầu của nó và sẽ không đăng nhập lại cũng như không an toàn cho chuỗi. Cũng lưu ý
rằng cấu trúc yycontext trình phân tích cú pháp được khởi tạo tự động lần đầu tiên
yyparse() được gọi là; cấu trúc này phải do đó được khởi tạo đúng cách bằng XNUMX
trước cuộc gọi đầu tiên tới yyparse().

YY_CTX_MEMBERS
Nếu YY_CTX_LOCAL được xác định (xem ở trên) thì macro YY_CTX_MEMBERS có thể được xác định
để mở rộng sang bất kỳ khai báo trường thành viên bổ sung nào mà khách hàng muốn
được đưa vào khai báo kiểu cấu trúc 'yycontext'. Những bổ sung này
các thành viên khác bị bỏ qua bởi trình phân tích cú pháp đã tạo. Bản sao của 'yycontext'
được liên kết với trình phân tích cú pháp hiện đang hoạt động có sẵn trong các hành động như
biến con trỏ yy.

YY_BUFFER_SIZE
Kích thước ban đầu của bộ đệm văn bản, tính bằng byte. Giá trị mặc định là 1024 và bộ đệm
kích thước được tăng gấp đôi bất cứ khi nào được yêu cầu để đáp ứng nhu cầu trong quá trình phân tích cú pháp. Một ứng dụng
thường phân tích cú pháp các chuỗi dài hơn nhiều có thể làm tăng điều này để tránh
tái phân bổ bộ đệm.

YY_STACK_SIZE
Kích thước ban đầu của ngăn xếp biến và hành động. Giá trị mặc định là 128, là
tăng gấp đôi bất cứ khi nào được yêu cầu để đáp ứng nhu cầu trong quá trình phân tích cú pháp. Các ứng dụng có
ngăn xếp cuộc gọi sâu với nhiều biến cục bộ hoặc thực hiện nhiều hành động sau một
kết hợp thành công duy nhất, có thể tăng điều này để tránh bộ đệm không cần thiết
tái phân bổ.

YY_MALLOC (YY, KÍCH THƯỚC)
Bộ cấp phát bộ nhớ cho tất cả bộ nhớ liên quan đến trình phân tích cú pháp. Các thông số là
cấu trúc yycontext hiện tại và số byte cần cấp phát. Mặc định
định nghĩa là: malloc (KÍCH THƯỚC)

YY_REALLOC (YY, PTR, KÍCH THƯỚC)
Bộ phân bổ lại bộ nhớ để lưu trữ phát triển động (chẳng hạn như bộ đệm văn bản và
ngăn xếp biến đổi). Các tham số là cấu trúc yycontext hiện tại,
bộ nhớ được phân bổ trước đó và số byte mà bộ nhớ đó sẽ
được lớn lên. Định nghĩa mặc định là: realloc (PTR, KÍCH THƯỚC)

YY_FREE (YY, PTR)
Bộ định vị bộ nhớ. Các tham số là cấu trúc yycontext hiện tại và
lưu trữ để phân bổ. Định nghĩa mặc định là: miễn phí (PTR)

YYPHÁT HÀNH
Tên của hàm giải phóng tất cả tài nguyên do cấu trúc yycontext nắm giữ.
Giá trị mặc định là 'yyrelease'.

Các biến sau đây có thể được tham chiếu trong các hành động.

xe tăng * yybuf
Biến này trỏ đến bộ đệm đầu vào của trình phân tích cú pháp được sử dụng để lưu trữ văn bản đầu vào có
chưa được khớp.

int vâng
Đây là phần bù (tính bằng yybuf) của ký tự tiếp theo được khớp và tiêu thụ.

xe tăng * yytext
Văn bản phù hợp gần đây nhất được phân tách bằng '<' và '>' được lưu trữ trong biến này.

int yylen
Biến này cho biết số ký tự trong 'yytext'.

yybối cảnh * yy
Biến này trỏ đến bản sao của 'yycontext' được liên kết với
trình phân tích cú pháp hiện đang hoạt động.

Các chương trình muốn giải phóng tất cả các tài nguyên được liên kết với trình phân tích cú pháp có thể sử dụng
chức năng sau đây.

yyrelease (yycontext*yy)
Trả về tất cả bộ nhớ do trình phân tích cú pháp phân bổ được liên kết với yy vào hệ thống. Kho lưu trữ
sẽ được phân bổ lại vào lần gọi tiếp theo tới yyparse().

Lưu ý rằng bộ nhớ cho chính cấu trúc yycontext không bao giờ được cấp phát hoặc lấy lại
ngầm hiểu. Ứng dụng phải phân bổ các cấu trúc này trong bộ lưu trữ tự động hoặc sử dụng
calloc() và tự do() để quản lý chúng một cách rõ ràng. Ví dụ trong phần sau
thể hiện một cách tiếp cận để quản lý tài nguyên.

CHÂN THÍ DỤ: MỞ RỘNG CÁC BỘ PHẬN CỦA BỐI CẢNH

yy biến được chuyển cho các hành động chứa trạng thái của trình phân tích cú pháp cộng với bất kỳ
các trường được xác định bởi YY_CTX_MEMBERS. Các trường luận án có thể được sử dụng để lưu trữ các ứng dụng cụ thể
thông tin toàn cầu cho một cuộc gọi cụ thể yyparse(). Một tầm thường nhưng đầy đủ Chân
ví dụ sau trong đó cấu trúc yycontext được mở rộng với tính trong số
các ký tự dòng mới được thấy trong đầu vào cho đến nay (nếu không thì ngữ pháp sẽ sử dụng và bỏ qua
toàn bộ đầu vào). Người gọi của yyparse() sử dụng tính để in số dòng của
đầu vào đã được đọc.

%{
#define YY_CTX_LOCAL 1
#xác định YY_CTX_MEMBERS
số int;
%}

Char = ('\ n' | '\ r \ n' | '\ r') {yy-> count ++}
| .

%%

#bao gồm
#bao gồm

int main ()
{
/ * tạo bối cảnh phân tích cú pháp cục bộ trong bộ nhớ tự động * /
yybối cảnh yy;
/ * ngữ cảnh * phải * được khởi tạo bằng XNUMX trước khi sử dụng lần đầu * /
memset (& yy, 0, sizeof (yy));

trong khi (yyparse (& yy))
;
printf ("% d newlines \ n", yy.count);

/ * giải phóng tất cả các tài nguyên liên quan đến ngữ cảnh * /
yyrelease (& yy);

0 trở về;
}

CHẨN ĐOÁN

peg và Chân cảnh báo về các điều kiện sau trong khi chuyển đổi ngữ pháp thành trình phân tích cú pháp.

cú pháp lôi
Ngữ pháp đầu vào không đúng định dạng theo một cách nào đó. Thông báo lỗi sẽ bao gồm
văn bản sắp được đối sánh (thường được sao lưu một lượng lớn từ vị trí thực tế của
lỗi) và số dòng của ký tự được coi là gần đây nhất (là
thường là vị trí thực của vấn đề).

loại trừ 'foo' đã sử dụng nhưng không xác định
Ngữ pháp đề cập đến một quy tắc có tên 'foo' nhưng không có định nghĩa nào cho nó được đưa ra.
Việc cố gắng sử dụng trình phân tích cú pháp đã tạo sẽ có thể dẫn đến lỗi từ trình liên kết
do các ký hiệu không xác định được liên kết với quy tắc bị thiếu.

loại trừ 'foo' xác định nhưng không đã sử dụng
Ngữ pháp đã xác định một quy tắc có tên 'foo' và sau đó bỏ qua nó. Mã liên kết
với quy tắc được bao gồm trong trình phân tích cú pháp đã tạo, ở tất cả các khía cạnh khác
được khỏe mạnh.

có thể vô hạn trái đệ quy in loại trừ 'foo'
Tồn tại ít nhất một đường dẫn thông qua ngữ pháp dẫn từ quy tắc 'foo'
quay lại (một lời gọi đệ quy của) cùng một quy tắc mà không sử dụng bất kỳ đầu vào nào.

Đệ quy trái, đặc biệt là được tìm thấy trong các tài liệu tiêu chuẩn, thường là 'trực tiếp' và
ngụ ý sự lặp lại tầm thường.

# (6.7.6)
trực tiếp-trừu tượng-khai báo =
Bộ khai báo trừu tượng LPAREN RPAREN
| trực tiếp-trừu tượng-khai báo? LBRACKET gán-expr? RBRACKET
| trực tiếp-trừu tượng-khai báo? VÒNG TAY NGÔI SAO LBRACKET
| trực tiếp-trừu tượng-khai báo? LPAREN param-type-list? RPAREN

Có thể dễ dàng loại bỏ đệ quy bằng cách chuyển đổi các phần của mẫu sau
đệ quy thành một hậu tố có thể lặp lại.

# (6.7.6)
trực tiếp-trừu tượng-khai báo =
trực tiếp-trừu tượng-khai báo-đầu?
trực tiếp-trừu tượng-khai báo-tail *

direct-trừu tượng-khai báo-head =
Bộ khai báo trừu tượng LPAREN RPAREN

direct-trừu tượng-khai báo-tail =
LBRACKET gán-expr? RBRACKET
| VÒNG TAY NGÔI SAO LBRACKET
| LPAREN param-loại-danh sách? RPAREN

THẬN TRỌNG

Một trình phân tích cú pháp chấp nhận đầu vào trống sẽ luôn luôn thành công. Hãy xem xét ví dụ sau,
không điển hình của nỗ lực đầu tiên để viết trình phân tích cú pháp dựa trên PEG:

Chương trình = Biểu thức *
Expression = "bất cứ điều gì"
%%
int main () {
trong khi (yyparse ())
put ("thành công!");
0 trở về;
}

Chương trình này lặp lại mãi mãi, không có vấn đề gì (nếu có) đầu vào được cung cấp trên stdin. Nhiều
có thể sửa chữa, cách dễ nhất là nhấn mạnh rằng trình phân tích cú pháp luôn sử dụng một số
đầu vào không trống. Thay đổi dòng đầu tiên thành

Chương trình = Biểu thức +

hoàn thành điều này. Nếu trình phân tích cú pháp được mong đợi sử dụng toàn bộ dữ liệu đầu vào, thì rõ ràng
yêu cầu cuối tệp cũng rất được khuyến khích:

Chương trình = Biểu thức + !.

Điều này hoạt động vì trình phân tích cú pháp sẽ chỉ không khớp với bất kỳ ký tự nào (vị từ "!")
(Biểu thức ".") khi nó cố gắng đọc vượt quá phần cuối của đầu vào.

Sử dụng chân trực tuyến bằng các dịch vụ onworks.net