1266639Sbapt-- $Id: README.BTYACC,v 1.2 2014/04/22 08:18:57 Tom.Shields Exp $ 2264790Sbapt 3264790SbaptThe original README from btyacc is below. 4264790Sbapt 5264790SbaptThe backtracking enhancements to byacc have been merged into Thomas Dickey's 6264790Sbaptbyacc baseline. 7264790Sbapt 8264790SbaptThe %include and %define/%ifdef enhancements described below are not currently 9264790Sbaptincorporated. 10264790Sbapt 11266639SbaptThe position management functionality ("YYPOSN", "yyposn", "YYREDUCEPOSNFUNC", 12266639Sbapt"YYREDUCEPOSNFUNCARG" & "YYCALLREDUCEPOSN") is replaced by a bison-compatible 13266639Sbapt"%locations" implementation. 14266639Sbapt 15266639SbaptThe memory management functionality ("YYDELETEVAL" & "YYDELETEPOSN") is 16266639Sbaptreplaced by a bison-compatible "%destructor" implementation. 17266639Sbapt 18266639SbaptThe detailed syntax error processing functionality ("YYERROR_DETAILED" 19266639Sbapt& "yyerror_detailed()") is subsumed by the bison-compatible "yyerror()" 20266639Sbaptimplementation, as modified by the %parse-param and %locations directives. 21266639Sbapt 22266639SbaptThe debugging macro "YYDBPR()" in the parser skeleton is renamed 23266639Sbapt"YYSTYPE_TOSTRING()". 24266639Sbapt 25264790Sbapt------------------------------------------------------------------------------- 26264790Sbapt BTYACC -- backtracking yacc 27264790Sbapt =========================== 28264790Sbapt 29264790SbaptBTYACC was created by Chris Dodd using ideas from many 30264790Sbaptplaces and lots of code from the Berkeley Yacc 31264790Sbaptdistribution, which is a public domain yacc clone put 32264790Sbapttogether by the good folks at Berkeley. This code is 33264790Sbaptdistributed with NO WARRANTY and is public domain. 34264790SbaptIt is certain to contain bugs, which you should 35264790Sbaptreport to: chrisd@collins.com. 36264790Sbapt 37264790SbaptVadim Maslov of Siber Systems <vadik@siber.com> 38264790Sbaptconsiderably modified BTYACC to make it suitable 39264790Sbaptfor production environment. 40264790Sbapt 41264790SbaptSeveral people have suggested bug fixes that 42264790Sbaptwere incorporated into BtYacc. 43264790Sbapt 44264790SbaptSee the README.BYACC files for more about 45264790SbaptBerkeley Yacc and other sources of info. 46264790Sbapt 47264790Sbapthttp://www.siber.com/btyacc/ is the current home of BtYacc. 48264790SbaptIt is provided courtesy of Siber Systems http://www.siber.com/. 49264790Sbapt 50264790Sbapt 51264790Sbapt Version 3.0 changes 52264790Sbapt ------------------- 53264790Sbapt by Vadim Maslov 54264790Sbapt 55264790SbaptChanges mostly occurred in btyaccpa.ske file that 56264790Sbaptcontains the parsing shift/reduce/backtrack algorithm. 57264790Sbapt 58264790SbaptVersion 3.0 innovations focus on: 59264790Sbapt- text position computation and propagation, 60264790Sbapt- industrial-strength error processing and recovery. 61264790Sbapt 62264790Sbapt 63264790Sbapt** Added mechanism for computing and propagating 64264790Sbapttext position of tokens and non-terminals. 65264790Sbapt 66264790SbaptCompilers often need to build AST trees such that every node 67264790Sbaptin a tree can relate to the parsed program source it came from. 68264790SbaptThe following applications are very likely to need this: 69264790Sbapt- debuggers that show actual source of the debugged program, 70264790Sbapt- source-to-source translators that want 71264790Sbapt unchanged parts of the tree to generate the unchanged code. 72264790Sbapt 73264790SbaptThe new YYPOSN mechanism added in this version of BtYacc 74264790Sbapthelps you in automating the text position computation 75264790Sbaptand in assigning the computed text positions to the AST. 76264790SbaptThis mechanism is successfully used in commercial 77264790Sbaptparsers and source-to-source translators. 78264790Sbapt 79264790SbaptIn standard Yaccs every token and every non-terminal 80264790Sbapthas an YYSTYPE semantic value attached to it. 81264790SbaptIn this new version every token and every non-terminal 82264790Sbaptalso has an YYPOSN text position attached to it. 83264790SbaptYYPOSN is a user-defined type that can be anything and 84264790Sbaptthat has a meaning of text position attached to 85264790Sbapttoken or non-terminal. 86264790Sbapt 87264790SbaptIn addition to semantic value stack BtYacc now maintains 88264790Sbapttext position stack. Behavior of the text position stack 89264790Sbaptis similar to the behavior of the semantic value stack. 90264790Sbapt 91264790SbaptIf using text position mechanism, 92264790Sbaptyou need to define the following: 93264790Sbapt 94264790SbaptYYPOSN Preprocessor variable that contains C/C++ type of 95264790Sbapt the text position attached to 96264790Sbapt every token and non-terminal. 97264790Sbapt 98264790Sbaptyyposn Global variable of type YYPOSN. 99264790Sbapt The lexer must assign text position of 100264790Sbapt the returned token to yyposn, just like it assigns 101264790Sbapt semantic value of the returned token to yylval. 102264790Sbapt 103264790SbaptYYREDUCEPOSNFUNC 104264790Sbapt Preprocessor variable that points to function that 105264790Sbapt is called after the grammar rule reduction 106264790Sbapt to reduce text positions located on the stack. 107264790Sbapt 108264790Sbapt This function is called by BtYacc to reduce text 109264790Sbapt positions. The function is called immediately after 110264790Sbapt the regular rule reduction occurs. 111264790Sbapt 112264790Sbapt The function has the following prototype: 113264790Sbapt void ReducePosn(YYPOSN &ret, 114264790Sbapt YYPOSN *terms, 115264790Sbapt YYSTYPE *term_vals, 116264790Sbapt int term_no, 117264790Sbapt int stk_pos, 118264790Sbapt int yychar, 119264790Sbapt YYPOSN &yyposn, 120264790Sbapt UserType extra); 121264790Sbapt 122264790Sbapt The function arguments are: 123264790Sbapt - ret 124264790Sbapt Reference to the text position returned by 125264790Sbapt the rule. The function must write the computed 126264790Sbapt text position returned by the rule to ret. 127264790Sbapt This is analogue of the $$ semantic value. 128264790Sbapt 129264790Sbapt - term_posns 130264790Sbapt Array of the right-hand side rule components 131264790Sbapt YYPOSN text positions. These are analogues of 132264790Sbapt $1, $2, ..., $N in the text position world. 133264790Sbapt 134264790Sbapt - term_vals 135264790Sbapt Array of the right-hand side (RHS) rule components 136264790Sbapt YYSTYPE values. These are the $1,...,$N themselves. 137264790Sbapt 138264790Sbapt - term_no 139264790Sbapt Number of the components in RHS of the reduced rule. 140264790Sbapt Equal to size of arrays term_posns and term_vals. 141264790Sbapt Also equal to N in $1,...,$N in the reduced rule. 142264790Sbapt 143264790Sbapt - stk_pos 144264790Sbapt YYSTYPE/YYPOSN stack position before the reduction. 145264790Sbapt 146264790Sbapt - yychar 147264790Sbapt Lookahead token that immediately follows 148264790Sbapt the reduced RHS components. 149264790Sbapt 150264790Sbapt - yyposn 151264790Sbapt YYPOSN of the token that immediately follows 152264790Sbapt the reduced RHS components. 153264790Sbapt 154264790Sbapt - extra 155264790Sbapt User-defined extra argument passed to ReducePosn. 156264790Sbapt 157264790Sbapt Typically this function extracts text positions from 158264790Sbapt the right-hand side rule components and either 159264790Sbapt assigns them to the returned $$ structure/tree or 160264790Sbapt if no $$ value is returned, puts them into 161264790Sbapt the ret text position from where 162264790Sbapt it will be picked up by the later reduced rules. 163264790Sbapt 164264790SbaptYYREDUCEPOSNFUNCARG 165264790Sbapt Extra user-defined argument passed to 166264790Sbapt the ReducePosn function. This argument can use 167264790Sbapt any variables defined in btyaccpa.ske. 168264790Sbapt 169264790Sbapt 170264790Sbapt** Added code to btyaccpa.ske that automatically cleans up 171264790Sbaptsemantic semantic values and text positions of tokens 172264790Sbaptand non-terminals that are discarded and deleted as 173264790Sbapta result of error processing. 174264790Sbapt 175264790SbaptIn the previous versions the discarded token and non-terminal 176264790Sbaptsemantic values were not cleaned that caused quite severe 177264790Sbaptleaks. The only way to fix it was to add garbage collection 178264790Sbaptto YYSTYPE class. 179264790Sbapt 180264790SbaptNow BtYacc skeleton calls delete functions for semantic 181264790Sbaptvalues and positions of the discarded tokens and 182264790Sbaptnon-terminals. 183264790Sbapt 184264790SbaptYou need to define the following functions that BtYacc 185264790Sbaptcalls when it needs to delete semantic value or text position. 186264790Sbapt 187264790SbaptYYDELETEVAL 188264790Sbapt User-defined function that is called by BtYacc 189264790Sbapt to delete semantic value of the token or non-terminal. 190264790Sbapt 191264790Sbapt The user-defined function must have the prototype: 192264790Sbapt void DeleteYYval(YYSTYPE v, int type); 193264790Sbapt v is semantic value to delete, 194264790Sbapt type is one of the following: 195264790Sbapt 0 discarding token 196264790Sbapt 1 discarding state 197264790Sbapt 2 cleaning up stack when aborting 198264790Sbapt 199264790SbaptYYDELETEPOSN 200264790Sbapt User-defined function that is called by BtYacc 201264790Sbapt to delete text position of the token or non-terminal. 202264790Sbapt 203264790Sbapt The user-defined function must have the prototype: 204264790Sbapt void DeleteYYposn(YYPOSN p, int type); 205264790Sbapt v is semantic value to delete, 206264790Sbapt type is one of the following: 207264790Sbapt 0 discarding token 208264790Sbapt 1 discarding state 209264790Sbapt 2 cleaning up stack when aborting 210264790Sbapt 211264790Sbapt 212264790Sbapt** User can define "detailed" syntax error processing 213264790Sbaptfunction that reports an *exact* position of 214264790Sbaptthe token that caused the error. 215264790Sbapt 216264790SbaptIf you define preprocessor variable YYERROR_DETAILED in 217264790Sbaptyour grammar then you need define the following 218264790Sbapterror processing function: 219264790Sbapt 220264790Sbaptvoid yyerror_detailed(char *text, 221264790Sbapt int errt, 222264790Sbapt YYSTYPE &errt_value, 223264790Sbapt YYPOSN &errt_posn); 224264790Sbapt 225264790SbaptIt receives the following arguments: 226264790Sbapttext Error message. 227264790Sbapterrt Code of the token that caused the error. 228264790Sbapterrt_value Value of the token that caused the error. 229264790Sbapterrt_posn Text position of token that caused error. 230264790Sbapt 231264790Sbapt 232264790Sbapt** Dropped compatibility with C. 233264790Sbapt 234264790SbaptCompatibility with C became increasingly difficult 235264790Sbaptto maintain as new features were added to btyaccpa.ske. 236264790SbaptSo we dropped it. If anybody wants to make the new version 237264790Sbaptcompatible with C, we would gladly accept the changes. 238264790Sbapt 239264790SbaptMeanwhile we expect that you use C++ to write grammar 240264790Sbaptactions and everything else in grammar files. 241264790SbaptSince C is (in a sense) subset of C++, your C-based 242264790Sbaptgrammar may work if you use C++ compiler to compile it. 243264790Sbapt 244264790Sbapt Version 3.0 bugs fixed 245264790Sbapt ---------------------- 246264790Sbapt 247264790SbaptMatthias Meixner <meixner@mes.th-darmstadt.de> fixed a bug: 248264790SbaptBtYacc does not correctly handle typenames, if one typename 249264790Sbaptis a prefix of another one and if this type is used after 250264790Sbaptthe longer one. In this case BTYacc produces invalid code. 251264790Sbapt 252264790Sbapt 253264790Sbapt Version 2.1 changes 254264790Sbapt ------------------- 255264790Sbapt by Vadim Maslov 256264790Sbapt 257264790Sbapt** Added preprocessor statements to BtYacc that are similar 258264790Sbaptin function and behavior to C/C++ preprocessor statements. 259264790Sbapt 260264790SbaptThese statements are used to: 261264790Sbapt 262264790Sbapt- Introduce modularity into a grammar by breaking it 263264790Sbapt into several *.y files and assembling different 264264790Sbapt grammars from the *.y modules using %include and %ifdef. 265264790Sbapt 266264790Sbapt- Have several versions of the same grammar 267264790Sbapt by using %ifdef and $endif. 268264790Sbapt 269264790Sbapt- To include automatically generated grammar fragment. 270264790Sbapt For instance, we use %include to include 271264790Sbapt automatically generated list of tokens. 272264790Sbapt 273264790SbaptPreprocessor statements are: 274264790Sbapt 275264790Sbapt%define <var-name> 276264790Sbapt Define preprocessor variable named <var-name>. 277264790Sbapt 278264790Sbapt%ifdef <var-name> 279264790Sbapt If preprocessor variable named <var-name> 280264790Sbapt is defined by %define, then process the text from 281264790Sbapt this %ifdef to the closing %endif. 282264790Sbapt 283264790Sbapt%endif 284264790Sbapt Closing bracket for %ifdef preprocessor statement. 285264790Sbapt Only one nesting level of %ifdef-%endif is allowed. 286264790Sbapt 287264790Sbapt%include <file-name> 288264790Sbapt Process contents of the file named <file-name>. 289264790Sbapt If <file-name> is a relative name, it is looked up 290264790Sbapt in a directory in which btyacc was started. 291264790Sbapt Only one nesting level of %include is allowed. 292264790Sbapt 293264790Sbapt 294264790Sbapt Version 2.0 changes 295264790Sbapt ------------------- 296264790Sbapt by Vadim Maslov 297264790Sbapt 298264790Sbapt 299264790Sbapt** Changed 16-bit short numbers to 32-bit int numbers in 300264790Sbaptgrammar tables, so that huge grammar tables (tables that 301264790Sbaptare larger than 32768 elements) resulting from huge 302264790Sbaptgrammars (Cobol grammar, for instance) can work correctly. 303264790SbaptYou need to have 32-bit integer to index table bigger than 304264790Sbapt32768 elements, 16-bit integer is not enough. 305264790Sbapt 306264790SbaptThe original BtYacc just generated non-working tables 307264790Sbaptlarger than 32768 elements without even notifying about 308264790Sbaptthe table overflow. 309264790Sbapt 310264790Sbapt 311264790Sbapt** Make error recovery work correctly when error happens 312264790Sbaptwhile processing nested conflicts. Original BtYacc could 313264790Sbaptinfinitely cycle in certain situations that involved error 314264790Sbaptrecovery while in nested conflict. 315264790Sbapt 316264790SbaptMore detailed explanation: when we have nested conflicts 317264790Sbapt(conflict that happens while trial-processing another 318264790Sbaptconflict), it leads btyacc into NP-complete searching of 319264790Sbaptconflict tree. The ultimate goal is YYVALID operator that 320264790Sbaptselects a particular branch of that tree as a valid one. 321264790Sbapt 322264790SbaptIf no YYVALID is found on the tree, then error recovery 323264790Sbapttakes over. The problem with this is that error recovery 324264790Sbaptis started in the same state context that exists on the 325264790Sbaptlast surveyed branch of the conflict tree. Sometimes this 326264790Sbaptlast branch may be of zero length and it results in 327264790Sbaptrecovering to exactly the same state as existed before 328264790Sbaptentering the conflict. BtYacc cycles then. 329264790Sbapt 330264790SbaptWe solved this problem by memorizing the longest path in 331264790Sbaptthe conflict tree while browsing it. If we ever get into 332264790Sbapterror recovery, we restore state that existed on the 333264790Sbaptlongest path. Effectively we say: if we have an error, 334264790Sbaptlet us move forward as far as we possibly could while we 335264790Sbaptwere browsing the conflict tree. 336264790Sbapt 337264790Sbapt 338264790Sbapt** Introduce YYVALID_NESTED operation in addition to 339264790Sbaptsimply YYVALID. When we have a nested conflict (conflict 340264790Sbaptwhile processing in trial mode for another conflict), we 341264790Sbaptwant to relate YYVALID to a particular level of conflict 342264790Sbaptbeing in trial. 343264790Sbapt 344264790SbaptSince we mostly anticipate only 2-level nested conflicts 345264790SbaptYYVALID_NESTED tells the parser to satisfy only the 346264790Sbaptinternal conflict. Therefore, in 1-level conflict 347264790Sbaptsituation YYVALID_NESTED acts like a regular YYVALID, but 348264790Sbaptin 2-level conflict it is a no-op and the other YYVALID 349264790Sbaptfor outer conflict will be searched for. 350264790Sbapt 351264790Sbapt 352264790Sbapt** Improved handling of situation where /tmp directory is 353264790Sbaptmissing. Original btyacc just died quietly when /tmp 354264790Sbaptdirectory was missing. We added code that states the 355264790Sbaptproblem explicitly. While on UNIX /tmp directory is always 356264790Sbaptpresent, it may be missing on WIN32 systems, therefore 357264790Sbaptdiagnosing this situation is important. 358264790Sbapt 359264790Sbapt 360264790Sbapt Version 1.0 changes: BackTracking 361264790Sbapt ================================= 362264790Sbapt by Chris Dodd 363264790Sbapt 364264790SbaptBTYACC is a modified version of yacc that supports 365264790Sbaptautomatic backtracking and semantic disambiguation to 366264790Sbaptparse ambiguous grammars, as well as syntactic sugar for 367264790Sbaptinherited attributes (which tend to introduce conflicts). 368264790SbaptWhenever a btyacc generated parser runs into a 369264790Sbaptshift-reduce or reduce-reduce error in the parse table, it 370264790Sbaptremembers the current parse point (yacc stack and input 371264790Sbaptstream state), and goes into trial parse mode. It then 372264790Sbaptcontinues parsing, ignoring most rule actions. If it runs 373264790Sbaptinto an error (either through the parse table or through 374264790Sbaptan action calling YYERROR), it backtracks to the most 375264790Sbaptrecent conflict point and tries a different alternative. 376264790SbaptIf it finds a successful parse (reaches the end of the 377264790Sbaptinput or an action calls YYVALID), it backtracks to the 378264790Sbaptpoint where it first entered trial parse mode, and 379264790Sbaptcontinues with a full parse (executing all actions), 380264790Sbaptfollowing the path of the successful trial. 381264790Sbapt 382264790SbaptActions in btyacc come in two flavors -- {}-actions, which 383264790Sbaptare only executed when not in trial mode, and []-actions 384264790Sbaptwhich are executed regardless of mode. There are also 385264790Sbaptinherited attributes, which look like arguments (they are 386264790Sbaptenclosed in "()") and act like []-actions. 387264790Sbapt 388264790SbaptWhat this buys you: 389264790Sbapt 390264790Sbapt* No more lexer feedback hack. In yacc grammars for C, a 391264790Sbaptstandard hack, know as the "lexer feedback hack" is used 392264790Sbaptto find typedef names. The lexer uses semantic 393264790Sbaptinformation to decide if any given identifier is a 394264790Sbapttypedef-name or not and returns a special token. With 395264790Sbaptbtyacc, you no longer need to do this; the lexer should 396264790Sbaptjust always return an identifier. The btyacc grammar then 397264790Sbaptneeds a rule of the form: 398264790Sbapt 399264790Sbapttypename: ID [ if (!IsTypeName(LookupId($1))) YYERROR; ] 400264790Sbapt 401264790SbaptWhile the hack works adequately well for parsing C, it 402264790Sbaptbecomes a nightmare when you try to parse something like 403264790SbaptC++, where treating an ID as a typedef becomes heavily 404264790Sbaptdependent on context. 405264790Sbapt 406264790Sbapt* Easy disambiguation via simple ordering. Btyacc runs 407264790Sbaptits trials via the rule "try shifting first, then try 408264790Sbaptreducing by the order that the conflicting rules appear in 409264790Sbaptthe input file". This means you can deal with semantic a 410264790Sbaptdisambiguation rule like: 411264790Sbapt [1] If it looks like a declaration it is, otherwise 412264790Sbapt [2] If it looks like an expression it is, otherwise 413264790Sbapt [3] it is a syntax error 414264790Sbapt [Ellis&Stroustrup, Annotated C++ Reference Manual, p93] 415264790Sbapt 416264790SbaptTo deal with this, you need only put all the rules for 417264790Sbaptdeclarations before the rules for expressions in the 418264790Sbaptgrammar file. 419264790Sbapt 420264790Sbapt* No extra cost if you do not use it. Backtracking is 421264790Sbaptonly triggered when the parse hits a shift/reduce or 422264790Sbaptreduce/reduce conflict in the table. If you have no 423264790Sbaptconflicts in your grammar, there is no extra cost, other 424264790Sbaptthan some extra code which will never be invoked. 425264790Sbapt 426264790Sbapt* C++ and ANSI C compatible parsers. The parsers produced 427264790Sbaptby btyacc can be compiled with C++ correctly. If you 428264790Sbapt"#define" YYSTYPE to be some C++ type with constructor and 429264790Sbaptdestructor, everything will work fine. My favorite is 430264790Sbapt"#define YYSTYPE SmartPointer", where SmartPointer is a 431264790Sbaptsmart pointer type that does garbage collection on the 432264790Sbaptpointed to objects. 433264790Sbapt 434264790SbaptBTYACC was originally written to make it easy to write a 435264790SbaptC++ parser (my goal was to be able to use the grammar out 436264790Sbaptof the back of the ARM with as few modifications as 437264790Sbaptpossible). Anyone who has ever looked at Jim Roskind 438264790Sbaptpublic domain C++ yacc grammar, or the yacc-based grammar 439264790Sbaptused in g++ knows how difficult this is. BTYACC is very 440264790Sbaptuseful for parsing any ambiguous grammar, particularly 441264790Sbaptones that come from trying to merge two (or more) complete 442264790Sbaptgrammars. 443264790Sbapt 444264790SbaptLimitations of the backtracking: Currently, the generated 445264790Sbaptparser does NO pruning of alternate parsing paths. To 446264790Sbaptavoid an exponential explosion of possible paths (and 447264790Sbaptparsing time), you need to manually tell the parser when 448264790Sbaptit can throw away saved paths using YYVALID. In practice, 449264790Sbaptthis turns out to be fairly easy to do. A C++ parser (for 450264790Sbaptexample) can just put a [YYVALID;] after every complete 451264790Sbaptdeclaration and statement rule, corresponding to pruning 452264790Sbaptthe backtracking state after seeing a ';' or '}' -- there 453264790Sbaptwill never be a situation in which it is useful to 454264790Sbaptbacktrack past either of these. 455264790Sbapt 456264790SbaptInherited attributes in btyacc: 457264790Sbapt 458264790SbaptInherited attributes look a lot like function arguments to 459264790Sbaptnon-terminals, which is what they end up being in a 460264790Sbaptrecursive descent parser, but NOT how they are implemented 461264790Sbaptin btyacc. Basically they are just syntactic sugar for 462264790Sbaptembedded semantic actions and $0, $-1, ... in normal yacc. 463264790Sbaptbtyacc gives you two big advantages besides just the 464264790Sbaptsyntax: 465264790Sbapt 1. it does type checking on the inherited attributes, 466264790Sbapt so you do not have to specify $<type>0 and makes sure 467264790Sbapt you give the correct number of arguments (inherited 468264790Sbapt attributes) to every use of a non-terminal. 469264790Sbapt 2. It "collapses" identical actions from that are produced 470264790Sbapt from inherited attributes. This eliminates many 471264790Sbapt potential reduce-reduce conflicts arising from 472264790Sbapt the inherited attributes. 473264790Sbapt 474264790SbaptYou use inherited attributes by declaring the types of the 475264790Sbaptattributes in the preamble with a type declaration and 476264790Sbaptdeclaring names of the attributes on the lhs of the yacc 477264790Sbaptrule. You can of course have more than one rule with the 478264790Sbaptsame lhs, and you can even give them different names in 479264790Sbapteach, but the type and number must be the same. 480264790Sbapt 481264790SbaptHere is a small example: 482264790Sbapt /* lhs takes 2 inherited attributes */ 483264790Sbapt%type <t1> lhs(<t1>, <t2>) 484264790Sbapt stuff(<t1>, <t2>) 485264790Sbapt%% 486264790Sbaptlhs($i1, $i2) : { $$ = $i1 } 487264790Sbapt | lhs($i1, $i2) stuff($1,$i2) { $$ = $2; } 488264790Sbapt 489264790SbaptThis is roughly equivalent to the following yacc code: 490264790Sbaptlhs : 491264790Sbapt { $$ = $<t1>-1; } 492264790Sbapt | lhs [ $<t1>$ = $-1; ] [ $<t2>$ = $<t2>0; ] stuff 493264790Sbapt { $$ = $4; } 494264790Sbapt ; 495264790Sbapt 496264790SbaptSee the file "test/t2.y" for a longer and more complete 497264790Sbaptexample. At the current time, the start symbol cannot 498264790Sbapthave any arguments. 499264790Sbapt 500264790SbaptVariant parsers: 501264790Sbapt 502264790SbaptBtyacc supports the -S flag to use a different parser 503264790Sbaptskeleton, changing the way that the parser is called and 504264790Sbaptused. The skeleton "push.skel" is included to produce a 505264790Sbapt"passive" parser that you feed tokens to (rather than 506264790Sbapthaving the parser call a separate yylex routine). With 507264790Sbaptpush.skel, yyparse is defined as follows: 508264790Sbapt 509264790Sbaptint yyparse(int token, YYSTYPE yylval) 510264790Sbapt 511264790SbaptYou should call yyparse repeatedly with successive tokens 512264790Sbaptof input. It returns 0 if more input is needed, 1 for a 513264790Sbaptsuccessful parse, and -1 for an unrecoverable parse error. 514264790Sbapt 515264790Sbapt 516264790Sbapt Miscellaneous Features in ver. 1.0 517264790Sbapt ---------------------------------- 518264790Sbapt by Chris Dodd 519264790Sbapt 520264790Sbapt The -r option has been implemented. The -r option tells 521264790SbaptYacc to put the read-only tables in y.tab.c and the code and 522264790Sbaptvariables in y.code.c. Keith Bostic asked for this option so 523264790Sbaptthat :yyfix could be eliminated. 524264790Sbapt 525264790Sbapt The -l and -t options have been implemented. The -l 526264790Sbaptoption tells Yacc not to include #line directives in the code 527264790Sbaptit produces. The -t option causes debugging code to be 528264790Sbaptincluded in the compiled parser. 529264790Sbapt 530264790Sbapt The code for error recovery has been changed to 531264790Sbaptimplement the same algorithm as AT&T Yacc. There will still 532264790Sbaptbe differences in the way error recovery works because AT&T 533264790SbaptYacc uses more default reductions than Berkeley Yacc. 534264790Sbapt 535264790Sbapt The environment variable TMPDIR determines the directory 536264790Sbaptwhere temporary files will be created. If TMPDIR is defined, 537264790Sbapttemporary files will be created in the directory whose 538264790Sbaptpathname is the value of TMPDIR. By default, temporary files 539264790Sbaptare created in /tmp. 540264790Sbapt 541264790Sbapt The keywords are now case-insensitive. For example, 542264790Sbapt%nonassoc, %NONASSOC, %NonAssoc, and %nOnAsSoC are 543264790Sbaptall equivalent. 544264790Sbapt 545264790Sbapt Commas and semicolons that are not part of C code are 546264790Sbapttreated as commentary. 547264790Sbapt 548264790Sbapt Line-end comments, as in BCPL, are permitted. Line-end 549264790Sbaptcomments begin with // and end at the next end-of-line. 550264790SbaptLine-end comments are permitted in C code; they are converted 551264790Sbaptto C comments on output. 552264790Sbapt 553264790Sbapt The form of y.output files has been changed to look more 554264790Sbaptlike those produced by AT&T Yacc. 555264790Sbapt 556264790Sbapt A new kind of declaration has been added. 557264790SbaptThe form of the declaration is 558264790Sbapt 559264790Sbapt %ident string 560264790Sbapt 561264790Sbaptwhere string is a sequence of characters beginning with a 562264790Sbaptdouble quote and ending with either a double quote or the 563264790Sbaptnext end-of-line, whichever comes first. The declaration 564264790Sbaptwill cause a #ident directive to be written near the start 565264790Sbaptof the output file. 566264790Sbapt 567264790Sbapt If a parser has been compiled with debugging code, that 568264790Sbaptcode can be enabled by setting an environment variable. 569264790SbaptIf the environment variable YYDEBUG is set to 0, debugging 570264790Sbaptoutput is suppressed. If it is set to 1, debugging output 571264790Sbaptis written to standard output. 572264790Sbapt 573264790Sbapt 574264790Sbapt Building BtYacc 575264790Sbapt --------------- 576264790Sbapt by Chris Dodd and Vadim Maslov 577264790Sbapt 578264790SbaptWe used GCC and GNU make to compile BtYacc both on UNIX and 579264790SbaptWIN32 paltforms. You are welcome to try different 580264790Sbaptcombinations of makes and compilers. Most likely it will 581264790Sbaptwork, but it may require Makefile changes. 582264790Sbapt 583264790SbaptThere is no config script. 584264790SbaptJust type "make" and it should compile. 585264790Sbapt 586264790SbaptAWK. If you want to change file btyaccpa.ske (backtracking 587264790Sbaptparser skeleton), you will need awk to compile it into 588264790Sbaptskeleton.c file. We used GNU AWK (gawk) version 3.0. 589264790Sbapt 590264790SbaptIt is known that using older versions of gawk 591264790Sbaptmay create problems in compilation, because older awks 592264790Sbapthave problems with backslashes at the end of a line. 593264790Sbapt 594264790SbaptFor MSDOS, there a "makefile.dos" that should do the trick. 595264790SbaptNote: makefile.dos was not tested for a long time. 596264790Sbapt 597264790SbaptThe result of compilation should be a single executable called 598264790Sbapt"btyacc" which you can install anywhere you like; 599264790Sbaptit does not require any other files in the distribution to run. 600264790Sbapt 601264790Sbapt 602264790Sbapt Legal Stuff 603264790Sbapt ----------- 604264790Sbapt by Chris Dodd and Vadim Maslov 605264790Sbapt 606264790SbaptIn English: BtYacc is freeware. BtYacc is distributed with 607264790Sbaptno warranty whatsoever. The author and any other contributors 608264790Sbapttake no responsibility for any and all consequences of its use. 609264790Sbapt 610264790SbaptIn Legalese: LIMITATION OF LIABILITY. NEITHER SIBER SYSTEMS 611264790SbaptNOR ANY OF ITS LICENSORS NOR ANY BTYACC CONTRIBUTOR SHALL BE 612264790SbaptLIABLE FOR ANY INDIRECT, INCIDENTAL, SPECIAL OR CONSEQUENTIAL 613264790SbaptDAMAGES, OR DAMAGES FOR LOSS OF PROFITS, REVENUE, DATA OR 614264790SbaptDATA USE, CAUSED BY BTYACC AND INCURRED BY CUSTOMER OR ANY 615264790SbaptTHIRD PARTY, WHETHER IN AN ACTION IN CONTRACT OR TORT, EVEN 616264790SbaptIF SIBER SYSTEMS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 617264790SbaptDAMAGES. 618