// ParserGenerator by Malcolm Crowe August 1995, 2000, 2003 // 2003 version (4.1+ of Tools) implements F. DeRemer & T. Pennello: // Efficient Computation of LALR(1) Look-Ahead Sets // ACM Transactions on Programming Languages and Systems // Vol 4 (1982) p. 615-649 // See class SymbolsGen in parser.cs using System; using System.Collections; using System.IO; using System.Text; using Tools; public class PrecReference : TOKEN { public CSymbol precref; public PrecReference(Lexer lx,TOKEN t) : base(lx) { precref = ((CSymbol)t).Resolve(); new SymbolType(((ptokens)lx).m_sgen,t.yytext,true); } } // This is an implementation of the Digraph algorithm from // F. DeRemer and T. Pennello "Efficient Computation of LALR(1) // Look-Ahead Sets" ACM Transactions on Programming Languages // and Systems 4 (1982) p.625 public class Digraph { public SymbolsGen sg; public Relation R; // defines the Digraph on the set of transitions public Func F1,F2; // we will compute F2 from F1 // such that F2(x) = F1(x) union Union{ F2(y) | xRy } // by adding elements to the F2 sets using public AddToFunc DF2; public Digraph(SymbolsGen s,Relation r,Func f1,Func f2,AddToFunc d) { sg=s; R=r; F1=f1; F2=f2; DF2=d; N = new int[sg.m_trans]; for (int j=0;j {1}",m_tok.yytext,m_tok.GetType().Name); while (m_tok!=null) ParseProduction(); // that's the end of the script if (!m_parserseen) Error(30,0,"no parser directive detected - possibly incorrect text encoding?"); m_outFile.WriteLine(m_actions); // output the action function m_outFile.WriteLine("} return null; }"); special.AddToRhs(m_symbols.m_startSymbol); special.AddToRhs(m_symbols.EOFSymbol); // 2: PROCESSING Console.WriteLine("First"); DoFirst(); Console.WriteLine("Follow"); DoFollow(); Console.WriteLine("Parse Table"); ParseState start = new ParseState(this,null); m_symbols.m_states[0] = start; start.MaybeAdd(new ProdItem(special,0)); start.Closure(); start.AddEntries(); Transition tfinal = (Transition)start.m_transitions[m_symbols.m_startSymbol.yytext]; ParserShift pe = tfinal.m_next; m_symbols.m_accept = pe.m_next; if (m_symbols.m_accept==null) m_symbols.erh.Error(new CSToolsFatalException(43,0,0,"","No accept state. ParserGenerator cannot continue.")); // 2A: Reduce States for the LR(0) parser foreach (ParseState ps in m_symbols.m_states.Values) ps.ReduceStates(); /* if (m_showParser) { foreach (ParseState ps in m_symbols.m_states.Values) { ps.Print0(); if (ps==m_symbols.m_accept) Console.WriteLine(" EOF accept"); } } */ // 3: Compute Look-ahead sets if (m_lalrParser) { m_symbols.Transitions(new Builder(Transition.BuildDR)); /* if (m_showParser) m_symbols.PrintTransitions(new Func(Transition.DR),"DR"); */ m_symbols.Transitions(new Builder(Transition.BuildReads)); new Digraph(this, new Relation(Transition.reads), new Func(Transition.DR), new Func(Transition.Read), new AddToFunc(Transition.AddToRead)).Compute(); // detect cycles in Read TBD /* if (m_showParser) m_symbols.PrintTransitions(new Func(Transition.Read),"Read"); */ m_symbols.Transitions(new Builder(Transition.BuildIncludes)); m_symbols.Transitions(new Builder(Transition.BuildLookback)); new Digraph(this, new Relation(Transition.includes), new Func(Transition.Read), new Func(Transition.Follow), new AddToFunc(Transition.AddToFollow)).Compute(); // detect cycles for which Read is non empty TBD /* if (m_showParser) m_symbols.PrintTransitions(new Func(Transition.Follow),"Follow"); */ m_symbols.Transitions(new Builder(Transition.BuildLA)); } // 5: OUTPUT // output the run-time ParsingInfo table Console.WriteLine("Building parse table"); m_symbols.Transitions(new Builder(Transition.BuildParseTable)); foreach (CSymbol v in m_symbols.symbols.Values) { if (v.m_symtype!=CSymbol.SymType.nodesymbol) continue; ParsingInfo pi = new ParsingInfo(v.yytext); CSymbol r = v; while (r.m_symtype==CSymbol.SymType.nodesymbol) r = r.m_refSymbol; if (m_symbols.symbolInfo[v.yytext]!=null) m_symbols.erh.Error(new CSToolsException(45,"Bad %node/%symbol hierarchy")); pi.m_parsetable = m_symbols.GetSymbolInfo(r.yytext).m_parsetable; m_symbols.symbolInfo[v.yytext] = pi; } Console.WriteLine("Writing the output file"); m_outFile.WriteLine("public yy"+m_outname+"():base() { arr = new byte[] { "); m_symbols.Emit(m_outFile); // output the class factories CSymbol s; Console.WriteLine("Class factories"); IDictionaryEnumerator de = m_symbols.symbols.GetEnumerator(); for (int pos = 0; pos3 && buf.Substring(0,3)=="//%") { gotit = true; if (buf.Substring(3,1)=="+") { m_lexer.yytext = buf.Substring(4); new SymbolType(this,m_lexer.yytext,true); } if (buf.Substring(3,1)=="|") { m_lexerClass = buf.Substring(4); } else { m_lexer.yytext = buf.Substring(3); new SymbolType(this,m_lexer.yytext,false); } } sr.Close(); if (!gotit) erh.Error(new CSToolsFatalException(27,1,0,"","%parser directive did not give a tokens file")); } catch (Exception e) { erh.Error(new CSToolsFatalException(27,1,0,fname,fname+": "+e.Message)); } } public TOKEN m_tok; // current input token as returned by Parser.Next public void Advance() { m_tok = (TOKEN)m_lexer.Next(); } public Production m_prod; // current production being parsed internal void DoFirst() { // Rule 1: terminals only Production p; foreach (CSymbol v in m_symbols.symbols.Values) { if (v.m_symtype==CSymbol.SymType.unknown) v.m_symtype = CSymbol.SymType.terminal; if (v.IsTerminal()) { v.m_first.CheckIn(v); if (!Find(v)) erh.Error(new CSToolsException(31,"Lexer script should define symbol "+ v.yytext)); } } foreach (CSymbol s in m_symbols.literals.Values) s.m_first.CheckIn(s); m_symbols.EOFSymbol.m_first.CheckIn(m_symbols.EOFSymbol); // Rule 2: Nonterminals with the rhs consisting only of actions int j,k; for (k=1;k"); ch = m_lexer.GetChar(); } if (ch=='$') { // ch = m_lexer.GetChar(); str += "yylval"; if (m_prod.m_lhs.m_defined) Error(36,m_lexer.m_pch,String.Format("Production {0}: symbol {1} has been typed, and should not use $$",m_prod.m_pno, m_prod.m_lhs.yytext)); return str; } if (ch=='-') { minus = true; // ch = m_lexer.GetChar(); } ix =1; if (ch<'0' || ch>'9') Error(37,m_lexer.m_pch,String.Format("expected $ or digit, got {0}",(char)ch)); else ix = minus?('0'-ch):(ch-'0'); for (ch = m_lexer.PeekChar(); ch>='0' && ch<='9'; m_lexer.Advance()) ix = ix*10+ (minus?('0'-ch):(ch-'0')); if (ix<=0) { str += String.Format("\n\t({0})(yyps.StackAt({0}).m_value)\n\t",type,ln-ix); if ((char)ch!='.') str += ".m_dollar"; } else m_prod.StackRef(ref str, ch, ix); return str; } string GetBracketedSeq(ref int ch,char cend) { // ch is the start bracket, already returned string str = ""; int quoteseen = 0; int brackets = 1; char cstart = (char)ch; str += cstart; //Console.WriteLine("GetBracketedSeq with {0}",str); while ((ch=m_lexer.GetChar())!=0) { if (ch==cstart) { if (quoteseen==0) brackets++; } else if (ch==cend) { if (quoteseen==0 && --brackets==0) goto labout; } else if ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||ch=='_') { m_lexer.UnGetChar(); TOKEN a = m_lexer.Next(); if (m_prod.m_alias.Contains(a.yytext)) { int ix = (int)m_prod.m_alias[a.yytext]; ch = m_lexer.PeekChar(); m_prod.StackRef(ref str,ch,ix); } else str += a.yytext; continue; } else switch(ch) { case '$': str += FixDollars(ref ch); continue; // don't add the ch case '\\': str += (char)ch; ch = m_lexer.GetChar(); break; case '\n': break; case '"': case '\'': if (quoteseen==0) // start of quoted string quoteseen = ch; else if (quoteseen==ch) // matching end of string quoteseen = 0; break; } str += (char)ch; } Error(38,m_lexer.m_pch,"EOF in Action: check bracket counts, quotes"); labout: str += cend; str = str.Replace("yyp","(("+m_outname+")yyq)"); return str; } public override void OldAction(ParserOldAction a) { int ch = '{'; a.m_symtype = CSymbol.SymType.oldaction; a.m_action = ++action; a.m_initialisation = GetBracketedSeq(ref ch,'}'); a.m_sym = (CSymbol)m_prod.m_lhs; NextNonWhite(out ch); if (ch==';'||ch=='|') { // an old action at the end is converted into a simple action m_lexer.yytext = "%"; ParserSimpleAction sa = new ParserSimpleAction(this); SimpleAction(sa); NewConstructor(ref sa.m_sym, ")"+a.m_initialisation); a.m_sym = (CSymbol)sa; sa.yytext += sa.m_sym.yytext; a.yytext = "#"+sa.yytext; a.m_action = -1; // mark the old action for deletion } } // parsing routines internal void ParseProduction() { TOKEN tok = m_tok; CSymbol lhs = null; try { lhs = ((CSymbol)m_tok).Resolve(); } catch(Exception e) { erh.Error(new CSToolsFatalException(45,tok,string.Format("Syntax error in Parser script - possibly extra semicolon?",e.Message))); } m_tok = lhs; if (m_tok.IsTerminal()) Error(39,m_tok.pos,string.Format("Illegal left hand side <{0}> for production",m_tok.yytext)); if (m_symbols.m_startSymbol==null) m_symbols.m_startSymbol = lhs; if (lhs.m_symtype==CSymbol.SymType.unknown) lhs.m_symtype = CSymbol.SymType.nonterminal; if ((!lhs.m_defined) && lhs.m_prods.Count==0) { // lhs not defined in %symbol statement and not previously a lhs // so declare it as a new symbol m_outFile.WriteLine("[Serializable] public class "+lhs.yytext+" : SYMBOL {"); m_outFile.WriteLine(" public "+lhs.yytext+"(Parser yyq):base(yyq) { }"); m_outFile.WriteLine(" public override string yyname() { return \""+lhs.yytext+"\"; }}"); } if (!Find(lhs)) new SymbolType(this,lhs.yytext); m_prod = new Production(this,lhs); m_lexer.yy_begin("rhs"); Advance(); if (!m_tok.Matches(":")) Error(40,m_tok.pos,String.Format("Colon expected for production {0}",lhs.yytext)); Advance(); RhSide(m_prod); while(m_tok!=null && m_tok.Matches("|")) { Advance(); m_prod = new Production(this,lhs); RhSide(m_prod); } if (m_tok==null || !m_tok.Matches(";")) Error(41,m_lexer.m_pch,"Semicolon expected"); Advance(); m_prod = null; m_lexer.yy_begin("YYINITIAL"); } public void RhSide(Production p) { CSymbol s; ParserOldAction a = null; // last old action seen while (m_tok!=null) { if (m_tok.Matches(";")) break; if (m_tok.Matches("|")) break; if (m_tok.Matches(":")) { Advance(); p.m_alias[m_tok.yytext] = p.m_rhs.Count; Advance(); } else if (m_tok is PrecReference) { if (p.m_rhs.Count==0) erh.Error(new CSToolsException(21,"%prec cannot be at the start of a right hand side")); PrecReference pr = (PrecReference)m_tok; CSymbol r = (CSymbol)p.m_rhs[p.m_rhs.Count-1]; r.m_prec = pr.precref.m_prec; Advance(); } else { s = (CSymbol)m_tok; if (s.m_symtype==CSymbol.SymType.oldaction) { if (a!=null) Error(42,s.pos,"adjacent actions"); a = (ParserOldAction)s; if (a.m_action<0) { // an OldAction that has been converted to a SimpleAction: discard it s = a.m_sym; // add the SimpleAction instead s.m_symtype = CSymbol.SymType.simpleaction; ParserSimpleAction sa = (ParserSimpleAction)s; } else // add it to the Actions function m_actions += String.Format("\ncase {0} : {1} break;", a.m_action, a.m_initialisation); a = null; } else if (s.m_symtype!=CSymbol.SymType.simpleaction) s = ((CSymbol)m_tok).Resolve(); p.AddToRhs(s); Advance(); } } Precedence.Check(p); } public static void Main(string[] argv) { bool Dflag = false; bool Kflag = false; bool Lflag = false; bool Cflag = false; int argc = argv.Length; int j; for (j = 0; argc>0 && argv[j][0]=='-'; j++,argc--) switch(argv[j][1]) { case 'D': Dflag = true; Kflag = true; break; // showParser case 'K': Kflag = true; break; // keep going case 'L': Lflag = true; break; // skip LALR phase case 'C': Cflag = true; break; // discard the concrete syntax } ErrorHandler erh = new ErrorHandler(!Kflag); // by default reduce/reduce errors abort the parser generator ParserGenerate parser = new ParserGenerate(erh); parser.m_showParser = Dflag; parser.m_lalrParser = !Lflag; parser.m_concrete = !Cflag; if (argc==1) parser.Create(argv[j]); else parser.Create("test.parser"); if (erh.counter==0) Console.WriteLine("ParserGenerate completed successfully"); else Console.WriteLine("Parser error count="+erh.counter); } }