<div dir="ltr"><div>I'd also recommend against Yacc. As others have said, it's a great tool and very powerful but a recursive descent parser will do the job 99% of the time and will be much easier. Writing a good unambiguous grammar for Yacc can be tricky and is much more difficult to debug than a recursive descent parser. A lot of languages now have "parser combinator" libraries which make it even easier to write a recursive descent parser. I'd do a google search to see if there's one available for your programming language of choice.</div><div><br></div><div>Unfortunately I don't have any tutorial recommendations I still have my compiler textbook from university (which is probably way more information than you need) so I haven't personally needed the sort of tutorial you're looking for.</div><div><br></div><div>On the other hand (and no promises), I've been trying to start a blog so if you can't find a good tutorial on recursive descent parsing let me know and I *might* find the time to write one myself.</div><div><br></div><div>Matt Gordon<br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Sun, Sep 16, 2018 at 1:47 PM D. Hugh Redelmeier via talk <<a href="mailto:talk@gtalug.org">talk@gtalug.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Ater advising against YACC, I thought I should promote it a bit.<br>
<br>
YACC uses a formal declarative system for specifying a language<br>
grammar (Backus-Naur Form).  This has a number of nice features:<br>
<br>
- BNF is very well described and extensively used in the literature<br>
<br>
- it was invented to describe the programming language Algol 60.<br>
  That document is one of the classics of computer science<br>
  and is still a must-read.  Here's a copy:<br>
        <<a href="https://www.masswerk.at/algol60/report.htm" rel="noreferrer" target="_blank">https://www.masswerk.at/algol60/report.htm</a>><br>
<br>
- many bastardizations of BNF have been used.  The real thing is better<br>
  than most of its successors.<br>
<br>
- a BNF grammar is a context-free grammar (Chomsky's term.  Yes, that<br>
  Noam Chomsky)<br>
<br>
- if a grammar is ambiguous, YACC will tell you.  Not at runtime but<br>
  at table-building time.  This is really really useful because it is<br>
  very easy to inadvertently create an ambiguous grammar -- generally<br>
  a Bad Thing.  Informal recursive descent parsers never detect such<br>
  problems.<br>
<br>
  This feature is especially useful for those still learning about<br>
  language design.<br>
<br>
- YACC has features to resolve ambiguities.  They are short-cuts that<br>
  cloud the issues and I think that they are a Bad Thing.<br>
<br>
- an LR(k) grammar (invented by Knuth before LALR) means that a<br>
  deterministic Left to Right single-pass parser (i.e. one without any<br>
  backtracking) can "recognize" the language with only a k-symbol<br>
  look-ahead.  LALR(k) is a subset of LR(k) for which it is known how<br>
  to generate an efficient parser.  In practical terms, k should be 1.<br>
<br>
- when given a choice between a declarative and a procedural model,<br>
  always at least consider declarative.  Declarative is much easier to<br>
  reason about as the system gets even a little complicated.<br>
<br>
One learns a lot about language design by writing a BNF grammar and<br>
debugging it through YACC.<br>
<br>
lex is based on some theory (Chomsky Type 0 (Regular) languages) but<br>
is more ad hoc.<br>
---<br>
Talk Mailing List<br>
<a href="mailto:talk@gtalug.org" target="_blank">talk@gtalug.org</a><br>
<a href="https://gtalug.org/mailman/listinfo/talk" rel="noreferrer" target="_blank">https://gtalug.org/mailman/listinfo/talk</a><br>
</blockquote></div>