PackCC
| Deweloperzy | Arihiro Yoshida |
|---|---|
| Napisane w | C |
| System operacyjny | Międzyplatformowe |
| Typ | Generator parsera |
| Licencja | Licencja MIT |
| Strona internetowa |
PackCC to generator parsera dla C . Jego główne cechy są następujące:
- Generuje parser w pisanym C z gramatyki opisanej w PEG ,
- Daje parserowi dużą wydajność dzięki parsowaniu pakietów ,
- Obsługuje bezpośrednie i pośrednie lewostronnie rekurencyjne reguły gramatyczne,
- Generuje parser bezpieczny dla wątków i reentrant ,
- Składa się tylko z jednego kompaktowego pliku źródłowego.
Gramatyka wyjściowego parsera może być opisana w PEG (Parsing Expression Grammar). PEG jest językiem parsowania z góry na dół i jest podobny do gramatyki wyrażeń regularnych . W porównaniu z językiem analizy oddolnej, takim jak Yacc , PEG jest znacznie bardziej intuicyjny i nie może być niejednoznaczny. PEG nie wymaga, tokenizacja była oddzielnym krokiem, a reguły tokenizacji można pisać w taki sam sposób, jak wszelkie inne reguły gramatyczne.
Wygenerowany parser może bardzo wydajnie analizować dane wejściowe przez parsowanie packrat. Parsowanie Packrat to rekurencyjny algorytm parsowania zejścia , który jest przyspieszany za pomocą zapamiętywania . Używając parsowania packrat, dowolne dane wejściowe mogą być analizowane w czasie liniowym. Jednak bez tego wynikowy parser mógłby wykazywać wykładniczą wydajność czasową w najgorszym przypadku ze względu na nieograniczoną zdolność przewidywania.
W przeciwieństwie do zwykłych parserów Packrat, PackCC może obsługiwać bezpośrednie i pośrednie lewostronnie rekurencyjne reguły gramatyczne. Dzięki temu zasady gramatyczne są znacznie bardziej intuicyjne.
Wygenerowany kod jest upiększony i tak łatwy do zrozumienia, jak to tylko możliwe. W rzeczywistości używa wielu instrukcji goto, ale przepływy sterowania są znacznie łatwiejsze do śledzenia niż burze spaghetti goto generowane przez niektóre inne generatory parserów.
Sam PackCC jest objęty licencją MIT, ale wygenerowany kod może być rozpowszechniany na dowolnej licencji lub może być używany w oprogramowaniu własnościowym.
Przykład pliku wejściowego
Kalkulator biurkowy. Zauważ, że uwzględniono lewostronnie rekurencyjne reguły gramatyczne.
Instrukcja % przedrostek "calc" <- _ e : expression _ EOL { printf ( "answer=%d \n " , e ); } / ( ! EOL . ) * EOL { printf ( "błąd \n " ); } wyrażenie <- e : termin { $$ =
e ; } wyraz <- l : wyraz _ '+' _ r : czynnik { $$ = l + r ; } / l : termin _ '-' _ r : czynnik { $$ = l - r ; } / e : czynnik { $$ = e ;
} czynnik <- l : czynnik _ '*' _ r : jednoargumentowy { $$ = l * r ; } / l : czynnik _ '/' _ r : jednoargumentowy { $$ = l / r ; } / e : jednoargumentowy { $$ = e ; } jednoargumentowy
<- '+' _ e : jednoargumentowy { $$ = + e ; } / '-' _ e : jednoargumentowy { $$ = - e ; } / e : podstawowy { $$ = e ; } podstawowy <- < [ 0-9 ] + > { $$ = atoi
( 1 $ ); } / '(' _ e : wyrażenie _ ')' { $$ = e ; } _ <- [ \ t ] * EOL <- '\n' / '\ r \ n ' / '\r' / ';' %% int main () { calc_context_t *
0
ctx = calc_create ( NULL ); while ( calc_parse ( ctx , NULL )); calc_destroy ( ctx ); powrót ; }