PEG(1) General Commands Manual PEG(1) (NAME) peg, leg - (SYNOPSIS) peg [-hvV -ooutput] [filename ...] leg [-hvV -ooutput] [filename ...] (DESCRIPTION) peg leg (recursive-descent) : . (Parsing Expression Grammar PEG) [Ford 2004] . peg PEG Ford leg PEG lex(1) yacc(1) . lex yacc peg leg (backtracking) (ordered choice) ( ) ( ) . peg filename ( filename ) . peg C yyparse() . C (include) (link) . yyparse() . yyparse() . 'yy' 'YY' . (namespace pollution) . ( 'yy' lex(1) yacc(1) .) (OPTIONS) peg leg : -h . -ooutput output . -P #line () . -v (verbose) . -V . (A SIMPLE EXAMPLE) peg ( 'start') "username" . start <- "username" ( .) yyparse() C "username" . yyparse() . ( yyparse() "username" .) 'start' "username" . start <- "username" / . yyparse() ( ). (actions) . ( ) <<>> . ( << >> phrase marker .) start <- "username" { printf("%s\n", getlogin()); } / < . > { putchar(yytext[0]); } "username" . . : "username" . ('<' '>') . yytext . username.peg peg -o username.c username.peg username.c . C : #include /* printf(), putchar() */ #include /* getlogin() */ #include "username.c" /* yyparse() */ int main() { while (yyparse()) /* repeat until EOF */ ; return 0; } . name <- pattern pattern . name name . "characters" . ANSI C characters . 'characters' . [characters] . (^) ( ). (-) ( ) . : [a-zA-Z_] : [^0-9] . . . ( pattern ) ( ) . { action } . C . . ( ) yytext . ( ) yytext yyleng . ( lex(1) .) < ( ) . yytext . > ( ) yytext . element / : element ? . . . element + . element . element . element * . element . element . ( ): & element element . element . ! element element . element . !. . '&' : &{ expression } expression C ( statement) . expression (true) <<>> . expression (false) <<>> . ( ) sequence () . . '/' . sequence-1 / sequence-2 / ... / sequence-N . . (#) () . ( ) ( ) . <<>> . <<>> ( << >>) <<>> . . ( ) . . ..SH " PEG PEG (PEG GRAMMAR FOR PEG GRAMMARS)" peg . . Grammar <- Spacing Definition+ EndOfFile Definition <- Identifier LEFTARROW Expression Expression <- Sequence ( SLASH Sequence )* Sequence <- Prefix* Prefix <- AND Action / ( AND | NOT )? Suffix Suffix <- Primary ( QUERY / STAR / PLUS )? Primary <- Identifier !LEFTARROW / OPEN Expression CLOSE / Literal / Class / DOT / Action / BEGIN / END Identifier <- < IdentStart IdentCont* > Spacing IdentStart <- [a-zA-Z_] IdentCont <- IdentStart / [0-9] Literal <- ['] < ( !['] Char )* > ['] Spacing / ["] < ( !["] Char )* > ["] Spacing Class <- '[' < ( !']' Range )* > ']' Spacing Range <- Char '-' Char / Char Char <- '\\' [abefnrtv'"\[\]\\] / '\\' [0-3][0-7][0-7] / '\\' [0-7][0-7]? / '\\' '-' / !'\\' . LEFTARROW <- '<-' Spacing SLASH <- '/' Spacing AND <- '&' Spacing NOT <- '!' Spacing QUERY <- '?' Spacing STAR <- '*' Spacing PLUS <- '+' Spacing OPEN <- '(' Spacing CLOSE <- ')' Spacing DOT <- '.' Spacing Spacing <- ( Space / Comment )* Comment <- '#' ( !EndOfLine . )* EndOfLine Space <- ' ' / '\t' / EndOfLine EndOfLine <- '\r\n' / '\n' / '\r' EndOfFile <- !. Action <- '{' < [^}]* > '}' Spacing BEGIN <- '<' Spacing END <- '>' Spacing LEG (LEG GRAMMARS) leg peg lex(1) yacc(1) . peg : %{ text... %} . text () '%{' '%}' C . name = pattern <<>> '<-' . rule-name (Hyphen) . C (underscore) . '-' . - = [ \t\n\r]* number = [0-9]+ - name = [a-zA-Z_][a-zA_Z_0-9]* - l-paren = '(' - r-paren = ')' - . seq-1 | seq-2 '/' '|' . peg name <- sequence-1 / sequence-2 / sequence-3 leg : name = sequence-1 | sequence-2 | sequence-3 ; ( - ). @{ action } <> (@) . (back-tracking) PEG '@' . ( .) yytext . exp ~ { action } ~{ action } ( C ) exp . . yytext yyleng yy ( "CUSTOMISING THE PARSER" ). exp . rule = e1 e2 e3 ~{ error("e[12] ok; e3 has failed"); } | ... rule = (e1 e2 e3) ~{ error("one of e[123] has failed"); } | ... pattern ; - pattern . %% text... '%%' ( ) . text '%%' C . $$ = value '$$' value ( ) . ( 'int' ). YYSTYPE . identifier:name ( '$$') name identifier . '$$' ':' ..SH " LEG: (LEG EXAMPLE: A DESK CALCULATOR)" leg ( C 'main') . . . %{ #include /* printf() */ #include /* 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:Sum { $$ = s; } Sum = l:Product ( PLUS r:Product { l += r; } | MINUS r:Product { l -= r; } )* { $$ = l; } Product = l:Value ( TIMES r:Value { l *= r; } | DIVIDE r:Value { l /= r; } )* { $$ = l; } Value = i:NUMBER { $$ = atoi(yytext); } | i:ID !ASSIGN { $$ = vars[i]; } | OPEN i:Expr CLOSE { $$ = i; } NUMBER = < [0-9]+ > - { $$ = atoi(yytext); } ID = < [a-z] > - { $$ = yytext[0] - 'a'; } ASSIGN = '=' - PLUS = '+' - MINUS = '-' - TIMES = '*' - DIVIDE = '/' - OPEN = '(' - CLOSE = ')' - - = [ \t]* EOL = '\n' | '\r\n' | '\r' | ';' %% int main() { while (yyparse()) ; return 0; } LEG LEG (LEG GRAMMAR FOR LEG GRAMMARS) leg . . grammar = - ( declaration | definition )+ trailer? end-of-file declaration = '%{' < ( !'%}' . )* > RPERCENT trailer = '%%' < .* > definition = identifier EQUAL expression SEMICOLON? expression = sequence ( BAR sequence )* sequence = error+ error = prefix ( TILDE action )? prefix = AND action | ( AND | NOT )? suffix suffix = primary ( QUERY | STAR | PLUS )? primary = identifier COLON identifier !EQUAL | identifier !EQUAL | OPEN expression CLOSE | literal | class | DOT | action | BEGIN | END identifier = < [-a-zA-Z_][-a-zA-Z_0-9]* > - literal = ['] < ( !['] char )* > ['] - | ["] < ( !["] char )* > ["] - class = '[' < ( !']' range )* > ']' - range = char '-' char | char char = '\\' [abefnrtv'"\[\]\\] | '\\' [0-3][0-7][0-7] | '\\' [0-7][0-7]? | !'\\' . action = '{' < braces* > '}' - braces = '{' braces* '}' | !'}' . EQUAL = '=' - COLON = ':' - SEMICOLON = ';' - BAR = '|' - AND = '&' - NOT = '!' - QUERY = '?' - STAR = '*' - PLUS = '+' - OPEN = '(' - CLOSE = ')' - DOT = '.' - BEGIN = '<' - END = '>' - TILDE = '~' - RPERCENT = '%}' - - = ( space | comment )* space = ' ' | '\t' | end-of-line comment = '#' ( !end-of-line . )* end-of-line end-of-line = '\r\n' | '\n' | '\r' end-of-file = !. . YYSTYPE (semantic value). <<$$>> <<>> (bound) <<:>> . <> . YYPARSE . <> . YYPARSEFROM . : . <> . ()yyparse : int yyparse() { return yyparsefrom(yy_foo); } <> . YY_INPUT(buf, result, max_size) . buf max_size . buf result . 0 result . YY_INPUT : #define YY_INPUT(buf, result, max_size) \ { \ int yyc= getchar(); \ result= (EOF == yyc) ? 0 : (*(buf)= yyc, 1); \ } YY_CTX_LOCAL ( ) (context) YY_INPUT . YY_DEBUG (stderr) . YY_BEGIN <> . <<<>> . (predicates) . : #define YY_BEGIN (yybegin= yypos, 1) 1 (<<>>) . YY_END <<>>> . << >> . #define YY_END (yyend= yypos, 1) YY_PARSE(T) (yyparse yyparsefrom) T . : #define YY_PARSE(T) T (global visibility) ()yyparse ()yyparsefrom . <> : #define YY_PARSE(T) static T YY_CTX_LOCAL <> . (thread-safe) . yyparse() <<* yycontext>> . . : #include #define YY_CTX_LOCAL #include "the-generated-parser.peg.c" int main() { yycontext ctx; memset(&ctx, 0, sizeof(yycontext)); while (yyparse(&ctx)); return 0; } (reentrant) (thread-safe) . yycontext yyparse() yyparse() . YY_CTX_MEMBERS YY_CTX_LOCAL ( ) YY_CTX_MEMBERS <> . . <> yy . YY_BUFFER_SIZE . 1024 . . YY_STACK_SIZE . 128 . . YY_MALLOC(YY, SIZE) . yycontext . : malloc(SIZE) YY_REALLOC(YY, PTR, SIZE) ( ). yycontext . : realloc(PTR, SIZE) YY_FREE(YY, PTR) . yycontext . : free(PTR) YYRELEASE yycontext . <> . : char *yybuf . int yypos ( yybuf) . char *yytext '<' '>' . int yyleng <> . yycontext *yy <> ..PP . yyrelease(yycontext*yy) yy . yyparse() . yycontext . (automatic storage) calloc() free() . . LEG: (LEG EXAMPLE: EXTENDING THE PARSER'S CONTEXT) yy (actions) YY_CTX_MEMBERS . yyparse() . leg yycontext count ( ). yyparse() count . %{ #define YY_CTX_LOCAL 1 #define YY_CTX_MEMBERS \ int count; %} Char = ('\n' | '\r\n' | '\r') { yy->count++ } | . %% #include #include int main() { /* create a local parser context in automatic storage */ yycontext yy; /* the context *must* be initialised to zero before first use*/ memset(&yy, 0, sizeof(yy)); while (yyparse(&yy)) ; printf("%d newlines\n", yy.count); /* release all resources associated with the context */ yyrelease(&yy); return 0; } (DIAGNOSTICS) peg leg . syntax error . ( ) ( ). rule 'foo' used but not defined 'foo' . (linker) . rule 'foo' defined but not used 'foo' . . possible infinite left recursion in rule 'foo' 'foo' ( ) . <<>> . # (6.7.6) direct-abstract-declarator = LPAREN abstract-declarator RPAREN | direct-abstract-declarator? LBRACKET assign-expr? RBRACKET | direct-abstract-declarator? LBRACKET STAR RBRACKET | direct-abstract-declarator? LPAREN param-type-list? RPAREN . # (6.7.6) direct-abstract-declarator = direct-abstract-declarator-head? direct-abstract-declarator-tail* direct-abstract-declarator-head = LPAREN abstract-declarator RPAREN direct-abstract-declarator-tail = LBRACKET assign-expr? RBRACKET | LBRACKET STAR RBRACKET | LPAREN param-type-list? RPAREN . PEG : Program = Expression* Expression = "whatever" %% int main() { while (yyparse()) puts("success!"); return 0; } ( ) stdin . . Program = Expression+ . (end-of-file) : Program = Expression+ !. (<>) ( <<.>>) . (BUGS) leg(1) 'man peg' . 'yy' 'YY' . . . ! ~ . lex(1) ( ()yywrap yyin ) . '#line' C . (SEE ALSO) D. Val Schorre, META II, a syntax-oriented compiler writing language, 19th ACM National Conference, 1964, pp. 41.301--41.311. (backtracking) . Alexander Birman, The TMG Recognition Schema, Ph.D. dissertation, Princeton, 1970. - (backtracking). Bryan Ford, Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, ACM SIGPLAN Symposium on Principles of Programming Languages, 2004. PEG . peg. lex(1) yacc(1) leg . peg leg . : http://piumarta.com/software/peg (AUTHORS) peg leg Ian Piumarta (first-name at last-name dot com) C . . Version 0.1 September 2013 PEG(1)