.\" Copyright (c) 2007 by Ian Piumarta.\" All rights reserved..\" .\" Permission is hereby granted, free of charge, to any person obtaining a.\" copy of this software and associated documentation files (the 'Software'),.\" to deal in the Software without restriction, including without limitation.\" the rights to use, copy, modify, merge, publish, distribute, and/or sell.\" copies of the Software, and to permit persons to whom the Software is.\" furnished to do so, provided that the above copyright notice(s) and this.\" permission notice appear in all copies of the Software.  Acknowledgement.\" of the use of this Software in supporting documentation would be.\" appreciated but is not required..\" .\" THE SOFTWARE IS PROVIDED 'AS IS'.  USE ENTIRELY AT YOUR OWN RISK..\" .\" Last edited: 2013-09-09 14:58:44 by piumarta on emilia.\".TH PEG 1 "September 2013" "Version 0.1".SH NAMEpeg, leg \- parser generators.SH SYNOPSIS.B peg.B [\-hvV \-ooutput].I [filename ...].sp 0.B leg.B [\-hvV \-ooutput].I [filename ...].SH DESCRIPTION.I pegand.I legare tools for generating recursive\-descent parsers: programs thatperform pattern matching on text.  They process a Parsing ExpressionGrammar (PEG) [Ford 2004] to produce a program that recognises legalsentences of that grammar..I pegprocesses PEGs written using the original syntax described by Ford;.I legprocesses PEGs written using slightly different syntax and conventionsthat are intended to make it an attractive replacement for parsersbuilt with.IR lex (1)and.IR yacc (1).Unlike.I lexand.IR yacc ,.I pegand.I legsupport unlimited backtracking, provide ordered choice as a means fordisambiguation, and can combine scanning (lexical analysis) andparsing (syntactic analysis) into a single activity..PP.I pegreads the specified.IR filename s,or standard input if no.IR filename sare given, for a grammar describing the parser to generate..I pegthen generates a C source file that defines a function.IR yyparse().This C source file can be included in, or compiled and then linkedwith, a client program.  Each time the client program calls.IR yyparse ()the parser consumes input text according to the parsing rules,starting from the first rule in the grammar..IR yyparse ()returns non\-zero if the input could be parsed according to thegrammar; it returns zero if the input could not be parsed..PPThe prefix 'yy' or 'YY' is prepended to all externally\-visible symbolsin the generated parser.  This is intended to reduce the risk ofnamespace pollution in client programs.  (The choice of 'yy' ishistorical; see.IR lex (1)and.IR yacc (1),for example.).SH OPTIONS.I pegand .I legprovide the following options:.TP.B \-hprints a summary of available options and then exits..TP.B \-ooutputwrites the generated parser to the file.B outputinstead of the standard output..TP.B \-vwrites verbose information to standard error while working..TP.B \-Vwrites version information to standard error then exits..SH A SIMPLE EXAMPLEThe following.I peginput specifies a grammar with a single rule (called 'start') that issatisfied when the input contains the string "username"..nf     start <\- "username" .fi(The quotation marks are.I notpart of the matched text; they serve to indicate a literal string tobe matched.)  In other words,.IR  yyparse ()in the generated C source will return non\-zero only if the next eightcharacters read from the input spell the word "username".  If theinput contains anything else,.IR yyparse ()returns zero and no input will have been consumed.  (Subsequent callsto.IR yyparse ()will also return zero, since the parser is effectively blocked lookingfor the string "username".)  To ensure progress we can add analternative clause to the 'start' rule that will match any singlecharacter if "username" is not found..nf     start <\- "username"           / . .fi.IR yyparse ()now always returns non\-zero (except at the very end of the input).  Todo something useful we can add actions to the rules.  These actionsare performed after a complete match is found (starting from the firstrule) and are chosen according to the 'path' taken through the grammarto match the input.  (Linguists would call this path a 'phrasemarker'.).nf     start <\- "username"    { printf("%s\\n", getlogin()); }           / < . >         { putchar(yytext[0]); } .fiThe first line instructs the parser to print the user's login namewhenever it sees "username" in the input.  If that match fails, thesecond line tells the parser to echo the next character on the inputthe standard output.  Our parser is now performing useful work: itwill copy the input to the output, replacing all occurrences of"username" with the user's account name..PPNote the angle brackets ('<' and '>') that were added to the secondalternative.  These have no effect on the meaning of the rule, butserve to delimit the text made available to the following action inthe variable.IR yytext ..PPIf the above grammar is placed in the file.BR username.peg ,running the command.nf     peg \-o username.c username.peg .fiwill save the corresponding parser in the file.BR username.c .To create a complete program this parser could be included by a Cprogram as follows..nf     #include <stdio.h>      /* printf(), putchar() */    #include <unistd.h>     /* getlogin() */     #include "username.c"   /* yyparse() */     int main()    {      while (yyparse())     /* repeat until EOF */        ;      return 0;    }.fi.SH PEG GRAMMARSA grammar consists of a set of named rules..nf     name <\- pattern .fiThe.B patterncontains one or more of the following elements..TP.B nameThe element stands for the entire pattern in the rule with the given.BR name ..TP.BR \(dq characters \(dqA character or string enclosed in double quotes is matched literally.The ANSI C escape sequences are recognised within the.IR characters ..TP.BR ' characters 'A character or string enclosed in single quotes is matched literally, as above..TP.BR [ characters ]A set of characters enclosed in square brackets matches any singlecharacter from the set, with escape characters recognised as above.If the set begins with an uparrow (^) then the set is negated (theelement matches any character.I notin the set).  Any pair of characters separated with a dash (\-)represents the range of characters from the first to the second,inclusive.  A single alphabetic character or underscore is matched bythe following set..nf     [a\-zA\-Z_] .fiSimilarly, the following matches  any single non\-digit character..nf     [^0\-9] .fi.TP.B .A dot matches any character.  Note that the only time this fails is atthe end of file, where there is no character to match..TP.BR ( \ pattern\  )Parentheses are used for grouping (modifying the precedence of theoperators described below)..TP.BR { \ action\  }Curly braces surround actions.  The action is arbitrary C source codeto be executed at the end of matching.  Any braces within the actionmust be properly nested.  Any input text that was matched before theaction and delimited by angle brackets (see below) is made availablewithin the action as the contents of the character array.IR yytext .The length of (number of characters in).I yytextis available in the variable.IR yyleng .(These variable names are historical; see.IR lex (1).).TP.B <An opening angle bracket always matches (consuming no input) andcauses the parser to begin accumulating matched text.  This text willbe made available to actions in the variable.IR yytext ..TP.B >A closing angle bracket always matches (consuming no input) and causesthe parser to stop accumulating text for.IR yytext ..PPThe above.IR element scan be made optional and/or repeatable with the following suffixes:.TP.RB element\  ?The element is optional.  If present on the input, it is consumed andthe match succeeds.  If not present on the input, no text is consumedand the match succeeds anyway..TP.RB element\  +The element is repeatable.  If present on the input, one or moreoccurrences of.I elementare consumed and the match succeeds.  If no occurrences of.I elementare present on the input, the match fails..TP.RB element\  *The element is optional and repeatable.  If present on the input, one or moreoccurrences of.I elementare consumed and the match succeeds.  If no occurrences of.I elementare present on the input, the match succeeds anyway..PPThe above elements and suffixes can be converted into predicates (thatmatch arbitrary input text and subsequently succeed or fail.I withoutconsuming that input) with the following prefixes:.TP.BR & \ elementThe predicate succeeds only if.I elementcan be matched.  Input text scanned while matching.I elementis not consumed from the input and remains available for subsequentmatching..TP.BR ! \ elementThe predicate succeeds only if.I elementcannot be matched.  Input text scanned while matching.I elementis not consumed from the input and remains available for subsequentmatching.  A popular idiom is.nf     !. .fiwhich matches the end of file, after the last character of the inputhas already been consumed..PPA special form of the '&' predicate is provided:.TP.BR & {\ expression\ }In this predicate the simple C.I expression.RB ( notstatement) is evaluated immediately when the parser reaches thepredicate.  If the.I expressionyields non\-zero (true) the 'match' succeeds and the parser continueswith the next element in the pattern.  If the.I expressionyields zero (false) the 'match' fails and the parser backs up to lookfor an alternative parse of the input..PPSeveral elements (with or without prefixes and suffixes) can becombined into a.I sequenceby writing them one after the other.  The entire sequence matches onlyif each individual element within it matches, from left to right..PPSequences can be separated into disjoint alternatives by thealternation operator '/'..TP.RB sequence\-1\  / \ sequence\-2\  / \ ...\  / \ sequence\-NEach sequence is tried in turn until one of them matches, at whichtime matching for the overall pattern succeeds.  If none of thesequences matches then the match of the overall pattern fails..PPFinally, the pound sign (#) introduces a comment (discarded) thatcontinues until the end of the line..PPTo summarise the above, the parser tries to match the input textagainst a pattern containing literals, names (representing otherrules), and various operators (written as prefixes, suffixes,juxtaposition for sequencing and and infix alternation operator) thatmodify how the elements within the pattern are matched.  Matches aremade from left to right, 'descending' into named sub\-rules as they areencountered.  If the matching process fails, the parser 'back tracks'('rewinding' the input appropriately in the process) to find thenearest alternative 'path' through the grammar.  In other words theparser performs a depth\-first, left\-to\-right search for the firstsuccessfully\-matching path through the rules.  If found, the actionsalong the successful path are executed (in the order they wereencountered)..PPNote that predicates are evaluated.I immediatelyduring the search for a successful match, since they contribute to thesuccess or failure of the search.  Actions, however, are evaluatedonly after a successful match has been found..SH PEG GRAMMAR FOR PEG GRAMMARSThe grammar for.I peggrammars is shown below.  This will both illustrate and formalisethe above description..nf     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 .fi.SH LEG GRAMMARS.I legis a variant of.I pegthat adds some features of.IR lex (1)and.IR yacc (1).It differs from.I pegin the following ways..TP.BI %{\  text... \ %}A declaration section can appear anywhere that a rule definition isexpected.  The.I textbetween the delimiters '%{' and '%}' is copied verbatim to thegenerated C parser code.I beforethe code that implements the parser itself..TP.IB name\  = \ patternThe 'assignment' operator replaces the left arrow operator '<\-'..TP.B rule\-nameHyphens can appear as letters in the names of rules.  Each hyphen isconverted into an underscore in the generated C source code.  A singlesingle hyphen '\-' is a legal rule name..nf     \-       = [ \\t\\n\\r]*    number  = [0\-9]+                 \-    name    = [a\-zA\-Z_][a\-zA_Z_0\-9]* \-    l\-paren = '('                    \-    r\-paren = ')'                    \-    .fiThis example shows how ignored whitespace can be obvious when readingthe grammar and yet unobtrusive when placed liberally at the end ofevery rule associated with a lexical element..TP.IB seq\-1\  | \ seq\-2The alternation operator is vertical bar '|' rather than forwardslash '/'.  The.I pegrule.nf     name <\- sequence\-1          / sequence\-2          / sequence\-3 .fiis therefore written.nf     name = sequence\-1         | sequence\-2         | sequence\-3         ; .fiin.I leg(with the final semicolon being optional, as described next)..TP.IB exp \ ~ \ {\ action\ }A postfix operator.BI ~ {\ action\ }can be placed after any expression and will behave like a normalaction (arbitrary C code) except that it is invoked only when.I expfails.  It binds less tightly than any other operator except alternation and sequencing, andis intended to make error handling and recovery code easier to write.Note that.I yytextand

Lines 1–500 of 1130. Load more