<div dir="ltr">i find that SD and yacc have about the same<div>time performance. yacc gets a bad rep when</div><div>it uses lex as its front-end. then it is pig-slow.</div><div><br></div></div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Mon, Mar 10, 2025 at 6:52 PM Larry McVoy <<a href="mailto:lm@mcvoy.com">lm@mcvoy.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I'm guessing this is because yacc makes it easy to fiddle with the grammar?<br>
Does performance factor in?<br>
<br>
I'm actually curious because BitKeeper has what we call a dspec language<br>
which lets you wander through the revision history and print it out in<br>
a sort of awk/printf like language.  If my memory serves me, we had a <br>
version in yacc (really flex but same thing) and Rob (cc-ed) rewrote <br>
it in a recursive-descent parser for performance reasons.  If you are<br>
curious, this is a dspec that spits out history in JSON format that <br>
I wrote because one of my engineers said it was impossible (it wasn't):<br>
<br>
<a href="http://mcvoy.com/lm/bkdocs/dspec-changes-json-v.txt" rel="noreferrer" target="_blank">http://mcvoy.com/lm/bkdocs/dspec-changes-json-v.txt</a><br>
<br>
$0 .. $9 are variables.  We used $if as a way to get an if statement<br>
rather than just say "if", :whatever: is a way to fish some field out<br>
of the history, Marc will get it, it's SCCS's :D: that means date, we<br>
just took it a lot further.<br>
<br>
I don't remember how much faster the RD version was but it was a lot,<br>
for sure more than a factor of 2 and maybe much more than that.  All<br>
I remember is at some point the dspec parser was a performance issue<br>
and after Rob rewrote it, it wasn't.<br>
<br>
On Mon, Mar 10, 2025 at 05:06:13PM -0700, Ken Thompson wrote:<br>
> re yacc vs RD<br>
> <br>
> i agree that they are about the same,<br>
> where the edge would tilt based on the parsed language.<br>
> BUT when the parsed language (like go) is not yet defined,<br>
> yacc is the only option.<br>
> <br>
> <br>
> <br>
> On Mon, Mar 10, 2025 at 4:50???PM Clem Cole <<a href="mailto:clemc@ccc.com" target="_blank">clemc@ccc.com</a>> wrote:<br>
> <br>
> > Marc - check out OpenSIMH( <a href="https://opensimh.org" rel="noreferrer" target="_blank">https://opensimh.org</a>)<br>
> > Check out over 40 different simulators including the I7000 which<br>
> > supports IBM 701,7010,7070,7080, 7090 - <a href="https://opensimh.org/simulators/" rel="noreferrer" target="_blank">https://opensimh.org/simulators/</a><br>
> ><br>
> ><br>
> > ???<br>
> ><br>
> > On Mon, Mar 10, 2025 at 7:12???PM Marc Rochkind <<a href="mailto:mrochkind@gmail.com" target="_blank">mrochkind@gmail.com</a>> wrote:<br>
> ><br>
> >> This thread started to be about what I thought were system programming<br>
> >> languages (e.g., C, BLISS) and seems to have meandered into a general<br>
> >> discussion of languages that were around in the 1960s and 1970s, so, what<br>
> >> the heck, I'll add my own story.<br>
> >><br>
> >> PL/0 is an education programming language introduced in the book, *Algorithms<br>
> >> + Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great<br>
> >> language for teaching compiler writing because it contains interesting<br>
> >> concepts, such as recursive functions, yet isn't overly complicated. I<br>
> >> wrote a PL/0 compiler for the IBM 701 (<br>
> >> <a href="https://github.com/MarcRochkind/pl0compiler" rel="noreferrer" target="_blank">https://github.com/MarcRochkind/pl0compiler</a>).<br>
> >><br>
> >> Yeah, that's not a misprint. I wrote perhaps the world's only 701<br>
> >> emulator (<a href="https://www.mrochkind.com/mrochkind/a-701.html" rel="noreferrer" target="_blank">https://www.mrochkind.com/mrochkind/a-701.html</a>), and my PL/0<br>
> >> compiler runs on it. Unfortunately, I can't verify that the compiled code<br>
> >> runs on an actual 701, since I'm sure there haven't been any in operation<br>
> >> for many decades. For those of you who haven't had the pleasure,<br>
> >> programming the 701 is really hard. It had no index registers, and the sign<br>
> >> bit didn't participate in shifts. Still, my compiler compiles full-blown<br>
> >> PL/0.<br>
> >><br>
> >> So there! ;-)<br>
> >><br>
> >> Marc Rochkind<br>
> >><br>
> >> On Mon, Mar 10, 2025 at 2:49???PM Bakul Shah via TUHS <<a href="mailto:tuhs@tuhs.org" target="_blank">tuhs@tuhs.org</a>><br>
> >> wrote:<br>
> >><br>
> >>> Perhaps the interviewer was looking for something dumb like the following<br>
> >>> and not a full RD parser?<br>
> >>><br>
> >>> int count = 0;<br>
> >>> while (*cp) {<br>
> >>>         char c = *cp++;<br>
> >>>         count += c == '(' ? 1 : c == ')' ? -1 : 0;<br>
> >>>         if (count < 0) return -1; // FAIL: one too many )<br>
> >>> }<br>
> >>> if (count > 0) return -1; // FAIL: too many (<br>
> >>> return 0; // SUCCESS<br>
> >>><br>
> >>> Though this will fall apart if you also want to also balance braces &/or<br>
> >>> brackets and must catch invalid cases like "(..[..)..]"!<br>
> >>><br>
> >>> > On Mar 10, 2025, at 8:19???AM, John Cowan <<a href="mailto:cowan@ccil.org" target="_blank">cowan@ccil.org</a>> wrote:<br>
> >>> ><br>
> >>> > I was working at the whiteboard during a job interview once. I had<br>
> >>> been asked to write a function to report if its input had balanced<br>
> >>> parentheses.  No problem: I wrote an RD parser in Python (which I prefer<br>
> >>> for whiteboarding) to detect balance and return True if the parse was<br>
> >>> successful and False if EOF was reached.<br>
> >>> ><br>
> >>> > I was starting to write some tests when the interviewer interrupted me.<br>
> >>> ><br>
> >>> > "What is that?"<br>
> >>> ><br>
> >>> > "It's a recursive descent parser. It detects if the input is<br>
> >>> well-formed."<br>
> >>> ><br>
> >>> > Blank look.<br>
> >>> ><br>
> >>> > I started to walk him through the code.<br>
> >>> ><br>
> >>> > He interrupted me. "Excuse me, I'll be back in a few minutes."<br>
> >>> ><br>
> >>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the<br>
> >>> recruiter will get back to you." That's the last I hear from them.<br>
> >>><br>
> >>><br>
> >><br>
> >> --<br>
> >> Subscribe to my Photo-of-the-Week emails at my website <a href="http://mrochkind.com" rel="noreferrer" target="_blank">mrochkind.com</a>.<br>
> >><br>
> ><br>
<br>
-- <br>
---<br>
Larry McVoy           Retired to fishing          <a href="http://www.mcvoy.com/lm/boat" rel="noreferrer" target="_blank">http://www.mcvoy.com/lm/boat</a><br>
</blockquote></div>