10 Mar
2025
10 Mar
'25
2:03 a.m.
everyone should write for their first compiler in
Pascal for a
simple language and no cheating using YACC. You need to write the whole
thing if you want to understand how parsing really works.
Yacc certainly makes it easier to write parsers for big grammars, but
it's far from cheating. You need to know a lot more about parsing to use
Yacc than you need to roll your own.
Hand parsing of a tiny grammar is almost a necessary step on the way to
understanding Yacc. But I think hand-building the whole parser for a
compiler is unnecessary torture--like doing trigonometry with log tables.
Doug
10 Mar
10 Mar
2:28 a.m.
New subject: What would early alternatives to C have been?
[While walking 5 miles through the snow …]
On Mar 9, 2025, at 9:03 PM, Douglas McIlroy
<douglas.mcilroy(a)dartmouth.edu> wrote:
In 1971 compiler construction course at UT-Austin, we had to use CDC Fortran to build a
compiler for a subset of Algol 60. Undergraduates used punch cards and RJE to the
6600/6400 shared by all but the privleged few.
Charlie
--
voice: +1.512.784.7526 e-mail: sauer(a)technologists.com
<mailto:sauer@technologists.com>
fax: +1.512.346.5240 web: https://technologists.com/sauer/
<http://technologists.com/sauer/>
Facebook/Google/LinkedIn/mas.to: CharlesHSauer
everyone should write for their first compiler in
Pascal for a
simple language and no cheating using YACC. You need to write the whole
thing if you want to understand how parsing really works.
Yacc certainly makes it easier to write parsers for big grammars, but it's far from
cheating. You need to know a lot more about parsing to use Yacc than you need to roll your
own.
Hand parsing of a tiny grammar is almost a necessary step on the way to understanding
Yacc. But I think hand-building the whole parser for a compiler is unnecessary
torture--like doing trigonometry with log tables.
Doug 
11 Mar
11 Mar
2:26 a.m.
New subject: uphill both ways, was Re: What would early alternatives to C have been?
It appears that Charles H. Sauer <sauer(a)technologists.com> said:
In 1971 compiler construction course at UT-Austin, we
had to use CDC Fortran to build a compiler for a subset of Algol 60. Undergraduates
used punch cards and RJE to the 6600/6400 shared by all but the privleged few.
In my 1971 compiler course at Yale, Alan Perlis made us try to write a compiler
that translated a subset of APL into Basic. He suggested we write it in APL,
which was a terrible idea, so I wrote it in Trac, for which I happened to have
written my own interpreter.
I think my compiler was the only one that worked, and it was pretty clever,
turning the APL array expressions into structures with array boundaries and
example expressions, with no array temporaries. It only generated the loops to
evaluate the expressions when storing into another array.
Someone got a PhD in 1978 for a similar compiling technique but in 1971 I was a
17 year old twerp so what did I know?
R's,
John
10 Mar
10 Mar
4:10 a.m.
New subject: What would early alternatives to C have been?
A rare case where I disagree with you, Doug. If the language is reasonably
regular (I do not mean in the strict Kleene sense), a recursive descent
parser is not much harder to write than a yacc grammar, and much smoother
at providing good error messages. Having done many yaccs and many RD
parsers, I no longer go to yacc.
To put it another way, there are few programming tasks I enjoy more than
writing a recursive descent parser for a sane language.
Now if the language is not so regular, my position might shift. I do recall
Bjarne dynamically editing the generated tables mid-parse to get yacc to
handle at least one stage of C++'s development.
Another way to think of it is that if you are designing the language and it
is undergoing frequent changes in grammar, yacc could certainly be move you
along faster. But even then once things had settled I'd still redo it as
RD, for the quality of the result.
You can credit Stephen R. "Software" Steve for this change in my thinking.
-rob
On Mon, Mar 10, 2025 at 1:12 PM Douglas McIlroy <
douglas.mcilroy(a)dartmouth.edu> wrote:
everyone
should write for their first compiler in Pascal for a
simple language and no cheating using YACC. You need to write the whole
thing if you want to understand how parsing really works.
Yacc certainly makes it easier to write parsers for big grammars, but
it's far from cheating. You need to know a lot more about parsing to use
Yacc than you need to roll your own.
Hand parsing of a tiny grammar is almost a necessary step on the way to
understanding Yacc. But I think hand-building the whole parser for a
compiler is unnecessary torture--like doing trigonometry with log tables.
Doug
3:19 p.m.
New subject: What would early alternatives to C have been?
I was working at the whiteboard during a job interview once. I had been
asked to write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.
On Mon, Mar 10, 2025, 12:10 AM Rob Pike <robpike(a)gmail.com> wrote:
A rare case where I disagree with you, Doug. If the
language is reasonably
regular (I do not mean in the strict Kleene sense), a recursive descent
parser is not much harder to write than a yacc grammar, and much smoother
at providing good error messages. Having done many yaccs and many RD
parsers, I no longer go to yacc.
To put it another way, there are few programming tasks I enjoy more than
writing a recursive descent parser for a sane language.
Now if the language is not so regular, my position might shift. I do
recall Bjarne dynamically editing the generated tables mid-parse to get
yacc to handle at least one stage of C++'s development.
Another way to think of it is that if you are designing the language and
it is undergoing frequent changes in grammar, yacc could certainly be move
you along faster. But even then once things had settled I'd still redo it
as RD, for the quality of the result.
You can credit Stephen R. "Software" Steve for this change in my thinking.
-rob
On Mon, Mar 10, 2025 at 1:12 PM Douglas McIlroy <
douglas.mcilroy(a)dartmouth.edu> wrote:
everyone
should write for their first compiler in Pascal for a
simple language and no cheating using YACC. You need to write the whole
thing if you want to understand how parsing really works.
Yacc certainly makes it easier to write parsers for big grammars, but
it's far from cheating. You need to know a lot more about parsing to use
Yacc than you need to roll your own.
Hand parsing of a tiny grammar is almost a necessary step on the way to
understanding Yacc. But I think hand-building the whole parser for a
compiler is unnecessary torture--like doing trigonometry with log tables.
Doug
7:56 p.m.
New subject: What would early alternatives to C have been?
On Mon, 10 Mar 2025, John Cowan wrote:
I was working at the whiteboard during a job interview
once. I had been
asked to write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was successful
and False if EOF was reached.
RD is a bit over the top, isn't it?
Pseudocode:
set counter to 0
while !EOF
do
read char
char == "(" -> counter++
char == ")" -> counter--
abort "Unbalanced: )" if counter < 0
done
abort "Unbalanced: (" if counter > 0
Untested, of course :-)
-- Dave
8:49 p.m.
New subject: What would early alternatives to C have been?
Perhaps the interviewer was looking for something dumb like the following
and not a full RD parser?
int count = 0;
while (*cp) {
char c = *cp++;
count += c == '(' ? 1 : c == ')' ? -1 : 0;
if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS
Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!
On Mar 10, 2025, at 8:19 AM, John Cowan
<cowan(a)ccil.org> wrote:
I was working at the whiteboard during a job interview once. I had been asked to write a
function to report if its input had balanced parentheses. No problem: I wrote an RD
parser in Python (which I prefer for whiteboarding) to detect balance and return True if
the parse was successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is
well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the recruiter
will get back to you." That's the last I hear from them.
11:12 p.m.
New subject: What would early alternatives to C have been?
This thread started to be about what I thought were system programming
languages (e.g., C, BLISS) and seems to have meandered into a general
discussion of languages that were around in the 1960s and 1970s, so, what
the heck, I'll add my own story.
PL/0 is an education programming language introduced in the book, *Algorithms
+ Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
language for teaching compiler writing because it contains interesting
concepts, such as recursive functions, yet isn't overly complicated. I
wrote a PL/0 compiler for the IBM 701 (
https://github.com/MarcRochkind/pl0compiler)
Yeah, that's not a misprint. I wrote perhaps the world's only 701 emulator (
https://www.mrochkind.com/mrochkind/a-701.html) and my PL/0 compiler runs
on it. Unfortunately, I can't verify that the compiled code runs on an
actual 701, since I'm sure there haven't been any in operation for many
decades. For those of you who haven't had the pleasure, programming the 701
is really hard. It had no index registers, and the sign bit didn't
participate in shifts. Still, my compiler compiles full-blown PL/0.
So there! ;-)
Marc Rochkind
On Mon, Mar 10, 2025 at 2:49 PM Bakul Shah via TUHS <tuhs(a)tuhs.org> wrote:
Perhaps the interviewer was looking for something dumb
like the following
and not a full RD parser?
int count = 0;
while (*cp) {
char c = *cp++;
count += c == '(' ? 1 : c == ')' ? -1 : 0;
if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS
Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!
--
Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
On Mar 10, 2025, at 8:19 AM, John Cowan
<cowan(a)ccil.org> wrote:
I was working at the whiteboard during a job interview once. I had been
asked to
write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is
well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.
11:49 p.m.
New subject: What would early alternatives to C have been?
Marc - check out OpenSIMH( https://opensimh.org)
Check out over 40 different simulators including the I7000 which
supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
ᐧ
On Mon, Mar 10, 2025 at 7:12 PM Marc Rochkind <mrochkind(a)gmail.com> wrote:
This thread started to be about what I thought were
system programming
languages (e.g., C, BLISS) and seems to have meandered into a general
discussion of languages that were around in the 1960s and 1970s, so, what
the heck, I'll add my own story.
PL/0 is an education programming language introduced in the book, *Algorithms
+ Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
language for teaching compiler writing because it contains interesting
concepts, such as recursive functions, yet isn't overly complicated. I
wrote a PL/0 compiler for the IBM 701 (
https://github.com/MarcRochkind/pl0compiler)
Yeah, that's not a misprint. I wrote perhaps the world's only 701 emulator
(https://www.mrochkind.com/mrochkind/a-701.html) and my PL/0 compiler
runs on it. Unfortunately, I can't verify that the compiled code runs on an
actual 701, since I'm sure there haven't been any in operation for many
decades. For those of you who haven't had the pleasure, programming the 701
is really hard. It had no index registers, and the sign bit didn't
participate in shifts. Still, my compiler compiles full-blown PL/0.
So there! ;-)
Marc Rochkind
On Mon, Mar 10, 2025 at 2:49 PM Bakul Shah via TUHS <tuhs(a)tuhs.org> wrote:
Perhaps the interviewer was looking for something
dumb like the following
and not a full RD parser?
int count = 0;
while (*cp) {
char c = *cp++;
count += c == '(' ? 1 : c == ')' ? -1 : 0;
if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS
Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!
--
Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
On Mar 10, 2025, at 8:19 AM, John Cowan
<cowan(a)ccil.org> wrote:
I was working at the whiteboard during a job interview once. I had been
asked to
write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is
well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.
11:58 p.m.
New subject: What would early alternatives to C have been?
Clem, thanks... didn't know about those.
MIne has two features that the other one perhaps doesn't: A fully
functional control panel, and it operates at the speed of the 701.
On Mon, Mar 10, 2025 at 5:49 PM Clem Cole <clemc(a)ccc.com> wrote:
Marc - check out OpenSIMH( https://opensimh.org)
Check out over 40 different simulators including the I7000 which
supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
11 Mar
11 Mar
12:06 a.m.
New subject: What would early alternatives to C have been?
re yacc vs RD
i agree that they are about the same,
where the edge would tilt based on the parsed language.
BUT when the parsed language (like go) is not yet defined,
yacc is the only option.
On Mon, Mar 10, 2025 at 4:50 PM Clem Cole <clemc(a)ccc.com> wrote:
Marc - check out OpenSIMH( https://opensimh.org)
Check out over 40 different simulators including the I7000 which
supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
ᐧ
On Mon, Mar 10, 2025 at 7:12 PM Marc Rochkind <mrochkind(a)gmail.com> wrote:
This thread started to be about what I thought
were system programming
languages (e.g., C, BLISS) and seems to have meandered into a general
discussion of languages that were around in the 1960s and 1970s, so, what
the heck, I'll add my own story.
PL/0 is an education programming language introduced in the book, *Algorithms
+ Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
language for teaching compiler writing because it contains interesting
concepts, such as recursive functions, yet isn't overly complicated. I
wrote a PL/0 compiler for the IBM 701 (
https://github.com/MarcRochkind/pl0compiler)
Yeah, that's not a misprint. I wrote perhaps the world's only 701
emulator (https://www.mrochkind.com/mrochkind/a-701.html) and my PL/0
compiler runs on it. Unfortunately, I can't verify that the compiled code
runs on an actual 701, since I'm sure there haven't been any in operation
for many decades. For those of you who haven't had the pleasure,
programming the 701 is really hard. It had no index registers, and the sign
bit didn't participate in shifts. Still, my compiler compiles full-blown
PL/0.
So there! ;-)
Marc Rochkind
On Mon, Mar 10, 2025 at 2:49 PM Bakul Shah via TUHS <tuhs(a)tuhs.org>
wrote:
Perhaps the interviewer was looking for something
dumb like the following
and not a full RD parser?
int count = 0;
while (*cp) {
char c = *cp++;
count += c == '(' ? 1 : c == ')' ? -1 : 0;
if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS
Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!
--
Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
On Mar 10, 2025, at 8:19 AM, John Cowan
<cowan(a)ccil.org> wrote:
I was working at the whiteboard during a job interview once. I had
been asked to
write a function to report if its input had balanced
parentheses. No problem: I wrote an RD parser in Python (which I prefer
for whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is
well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.
1:35 a.m.
New subject: What would early alternatives to C have been?
I'm guessing this is because yacc makes it easy to fiddle with the grammar?
Does performance factor in?
I'm actually curious because BitKeeper has what we call a dspec language
which lets you wander through the revision history and print it out in
a sort of awk/printf like language. If my memory serves me, we had a
version in yacc (really flex but same thing) and Rob (cc-ed) rewrote
it in a recursive-descent parser for performance reasons. If you are
curious, this is a dspec that spits out history in JSON format that
I wrote because one of my engineers said it was impossible (it wasn't):
http://mcvoy.com/lm/bkdocs/dspec-changes-json-v.txt
$0 .. $9 are variables. We used $if as a way to get an if statement
rather than just say "if", :whatever: is a way to fish some field out
of the history, Marc will get it, it's SCCS's :D: that means date, we
just took it a lot further.
I don't remember how much faster the RD version was but it was a lot,
for sure more than a factor of 2 and maybe much more than that. All
I remember is at some point the dspec parser was a performance issue
and after Rob rewrote it, it wasn't.
On Mon, Mar 10, 2025 at 05:06:13PM -0700, Ken Thompson wrote:
re yacc vs RD
i agree that they are about the same,
where the edge would tilt based on the parsed language.
BUT when the parsed language (like go) is not yet defined,
yacc is the only option.
On Mon, Mar 10, 2025 at 4:50???PM Clem Cole <clemc(a)ccc.com> wrote:
> Marc - check out OpenSIMH( https://opensimh.org)
> Check out over 40 different simulators including the I7000 which
> supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
>
>
> ???
>
> On Mon, Mar 10, 2025 at 7:12???PM Marc Rochkind <mrochkind(a)gmail.com> wrote:
>
>> This thread started to be about what I thought were system programming
>> languages (e.g., C, BLISS) and seems to have meandered into a general
>> discussion of languages that were around in the 1960s and 1970s, so, what
>> the heck, I'll add my own story.
>>
>> PL/0 is an education programming language introduced in the book, *Algorithms
>> + Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
>> language for teaching compiler writing because it contains interesting
>> concepts, such as recursive functions, yet isn't overly complicated. I
>> wrote a PL/0 compiler for the IBM 701 (
>> https://github.com/MarcRochkind/pl0compiler)
>>
>> Yeah, that's not a misprint. I wrote perhaps the world's only 701
>> emulator (https://www.mrochkind.com/mrochkind/a-701.html) and my PL/0
>> compiler runs on it. Unfortunately, I can't verify that the compiled code
>> runs on an actual 701, since I'm sure there haven't been any in
operation
>> for many decades. For those of you who haven't had the pleasure,
>> programming the 701 is really hard. It had no index registers, and the sign
>> bit didn't participate in shifts. Still, my compiler compiles full-blown
>> PL/0.
>>
>> So there! ;-)
>>
>> Marc Rochkind
>>
>> On Mon, Mar 10, 2025 at 2:49???PM Bakul Shah via TUHS <tuhs(a)tuhs.org>
>> wrote:
>>
>>> Perhaps the interviewer was looking for something dumb like the following
>>> and not a full RD parser?
>>>
>>> int count = 0;
>>> while (*cp) {
>>> char c = *cp++;
>>> count += c == '(' ? 1 : c == ')' ? -1 : 0;
>>> if (count < 0) return -1; // FAIL: one too many )
>>> }
>>> if (count > 0) return -1; // FAIL: too many (
>>> return 0; // SUCCESS
>>>
>>> Though this will fall apart if you also want to also balance braces
&/or
>>> brackets and must catch invalid cases like "(..[..)..]"!
>>>
>>> > On Mar 10, 2025, at 8:19???AM, John Cowan <cowan(a)ccil.org>
wrote:
>>> >
>>> > I was working at the whiteboard during a job interview once. I had
>>> been asked to write a function to report if its input had balanced
>>> parentheses. No problem: I wrote an RD parser in Python (which I prefer
>>> for whiteboarding) to detect balance and return True if the parse was
>>> successful and False if EOF was reached.
>>> >
>>> > I was starting to write some tests when the interviewer interrupted
me.
>>> >
>>> > "What is that?"
>>> >
>>> > "It's a recursive descent parser. It detects if the input is
>>> well-formed."
>>> >
>>> > Blank look.
>>> >
>>> > I started to walk him through the code.
>>> >
>>> > He interrupted me. "Excuse me, I'll be back in a few
minutes."
>>> >
>>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you,
the
>>> recruiter will get back to you." That's the last I hear from
them.
>>>
>>>
>>
>> --
>> Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
>>
>
--
---
Larry McVoy Retired to fishing http://www.mcvoy.com/lm/boat
5:07 a.m.
New subject: What would early alternatives to C have been?
i find that SD and yacc have about the same
time performance. yacc gets a bad rep when
it uses lex as its front-end. then it is pig-slow.
On Mon, Mar 10, 2025 at 6:52 PM Larry McVoy <lm(a)mcvoy.com> wrote:
I'm guessing this is because yacc makes it easy
to fiddle with the grammar?
Does performance factor in?
I'm actually curious because BitKeeper has what we call a dspec language
which lets you wander through the revision history and print it out in
a sort of awk/printf like language. If my memory serves me, we had a
version in yacc (really flex but same thing) and Rob (cc-ed) rewrote
it in a recursive-descent parser for performance reasons. If you are
curious, this is a dspec that spits out history in JSON format that
I wrote because one of my engineers said it was impossible (it wasn't):
http://mcvoy.com/lm/bkdocs/dspec-changes-json-v.txt
$0 .. $9 are variables. We used $if as a way to get an if statement
rather than just say "if", :whatever: is a way to fish some field out
of the history, Marc will get it, it's SCCS's :D: that means date, we
just took it a lot further.
I don't remember how much faster the RD version was but it was a lot,
for sure more than a factor of 2 and maybe much more than that. All
I remember is at some point the dspec parser was a performance issue
and after Rob rewrote it, it wasn't.
On Mon, Mar 10, 2025 at 05:06:13PM -0700, Ken Thompson wrote:
re yacc vs RD
i agree that they are about the same,
where the edge would tilt based on the parsed language.
BUT when the parsed language (like go) is not yet defined,
yacc is the only option.
On Mon, Mar 10, 2025 at 4:50???PM Clem Cole <clemc(a)ccc.com> wrote:
> Marc - check out OpenSIMH( https://opensimh.org)
> Check out over 40 different simulators including the I7000 which
> supports IBM 701,7010,7070,7080, 7090 -
https://opensimh.org/simulators/
>
>
> ???
>
> On Mon, Mar 10, 2025 at 7:12???PM Marc Rochkind <mrochkind(a)gmail.com>
wrote:
>
>> This thread started to be about what I thought were system programming
>> languages (e.g., C, BLISS) and seems to have meandered into a general
>> discussion of languages that were around in the 1960s and 1970s, so,
what
>> the heck, I'll add my own story.
>>
>> PL/0 is an education programming language introduced in the book,
*Algorithms
>> + Data Structures = Programs*, by
Niklaus Wirth in 1976. It's a great
>> language for teaching compiler writing because it contains interesting
>> concepts, such as recursive functions, yet isn't overly complicated. I
>> wrote a PL/0 compiler for the IBM 701 (
>> https://github.com/MarcRochkind/pl0compiler)
>>
>> Yeah, that's not a misprint. I wrote perhaps the world's only 701
>> emulator (https://www.mrochkind.com/mrochkind/a-701.html) and my
PL/0
>> compiler runs on it. Unfortunately, I
can't verify that the compiled
code
>> runs on an actual 701, since I'm
sure there haven't been any in
operation
>> for many decades. For those of you who
haven't had the pleasure,
>> programming the 701 is really hard. It had no index registers, and
the
sign
>> bit didn't participate in shifts.
Still, my compiler compiles
full-blown
>> PL/0.
>>
>> So there! ;-)
>>
>> Marc Rochkind
>>
>> On Mon, Mar 10, 2025 at 2:49???PM Bakul Shah via TUHS <tuhs(a)tuhs.org>
>> wrote:
>>
>>> Perhaps the interviewer was looking for something dumb like the
following
>>> and not a full RD parser?
>>>
>>> int count = 0;
>>> while (*cp) {
>>> char c = *cp++;
>>> count += c == '(' ? 1 : c == ')' ? -1 : 0;
>>> if (count < 0) return -1; // FAIL: one too many )
>>> }
>>> if (count > 0) return -1; // FAIL: too many (
>>> return 0; // SUCCESS
>>>
>>> Though this will fall apart if you also want to also balance braces
&/or
>>> brackets and must catch invalid
cases like "(..[..)..]"!
>>>
>>> > On Mar 10, 2025, at 8:19???AM, John Cowan <cowan(a)ccil.org>
wrote:
>>> >
>>> > I was working at the whiteboard during a job interview once. I had
>>> been asked to write a function to report if its input had balanced
>>> parentheses. No problem: I wrote an RD parser in Python (which I
prefer
>>> for whiteboarding) to detect balance
and return True if the parse was
>>> successful and False if EOF was reached.
>>> >
>>> > I was starting to write some tests when the interviewer
interrupted me.
>>> >
>>> > "What is that?"
>>> >
>>> > "It's a recursive descent parser. It detects if the input is
>>> well-formed."
>>> >
>>> > Blank look.
>>> >
>>> > I started to walk him through the code.
>>> >
>>> > He interrupted me. "Excuse me, I'll be back in a few
minutes."
>>> >
>>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you,
the
>>> recruiter will get back to
you." That's the last I hear from them.
>>>
>>>
>>
>> --
>> Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
>>
>
--
---
Larry McVoy Retired to fishing
http://www.mcvoy.com/lm/boat
5:15 a.m.
New subject: What would early alternatives to C have been?
Very probably. But under pressure I went with what I knew I could get
right. In hindsight it was like one of those non-quantitative
multiple-choice tests where you have to figure out not the correct answer
but the answer that the test author is most likely to believe to be correct.
On Mon, Mar 10, 2025, 4:49 PM Bakul Shah <bakul(a)iitbombay.org> wrote:
Perhaps the interviewer was looking for something dumb
like the following
and not a full RD parser?
int count = 0;
while (*cp) {
char c = *cp++;
count += c == '(' ? 1 : c == ')' ? -1 : 0;
if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS
Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!
On Mar 10, 2025, at 8:19 AM, John Cowan
<cowan(a)ccil.org> wrote:
I was working at the whiteboard during a job interview once. I had been
asked to
write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is
well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.
12 Mar
12 Mar
1:36 a.m.
New subject: parsing tools, was What would early alternatives
According to Ken Thompson <kenbob(a)gmail.com>:
-=-=-=-=-=-
i find that SD and yacc have about the same
time performance. yacc gets a bad rep when
it uses lex as its front-end. then it is pig-slow.
Parsing is never a performance issue since its time is generally O(n)
where n is the number of tokens emitted by the lexer and the constant
is not large. The lexer always is because it's the only part of the
compiler that has to look at every input character separately. If a
compiler does a lot of optimization, the analysis for that can be
slow, too.
Lex was a dog. Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.
--
Regards,
John Levine, johnl(a)taugh.com, Primary Perpetrator of "The Internet for
Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
2:22 a.m.
New subject: parsing tools, was What would early alternatives
Lex was a dog. Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.
Yes, "it's true what they say about lex" was a common phrase. (I think I
first saw it in the pathalias paper.)
There was a Usenix presentation -- late 80's (Washington?) but I couldn't
find it. -- by Vern Paxson about his rewrite called flex. I think he said
that the main reason lex was slow was the clever folding it had to do of
its internal tables to fit. Sadly Vern never got his paper in, but the
presentation showed a group with three lines, one at the top being slow
lex, the next two much lower on the Y axis being very close. He said the
second line was flex. Someone said what about the third, fastest, line? His
answer "that's cat"
Vern worked with Van on early network improvements (web-search the both of
them for a fun time).
Flex first posted to Usenet in 1988,
https://groups.google.com/g/comp.sources.unix/c/LZ_EHqd7XBg
3:35 a.m.
New subject: parsing tools, was What would early alternatives
On Tue, Mar 11, 2025 at 10:22:00PM -0400, Rich Salz wrote:
Vern worked with Van on early network improvements
(web-search the both of
them for a fun time).
Van was my networking hero until Drew at Netfix did the two side by side
stacks. I'm not sure who is better, but I'm sure they are both better
than me and I don't suck. I agree with Rich, check Van out, check Drew
out.
4:35 p.m.
New subject: parsing tools, was What would early alternatives
On Tue, 11 Mar 2025, Rich Salz wrote:
Maybe, maybe not just great programming.
It was mostly written by a summer student named Eric Schmidt. I wonder
what happened to him.
Regards,
John Levine, johnl(a)taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly
Lex was a dog.
Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.
There was a Usenix presentation -- late
80's (Washington?) but I couldn't
find it. -- by Vern Paxson about his rewrite called flex. I think he said
that the main reason lex was slow was the clever folding it had to do of
its internal tables to fit. 
5:11 a.m.
New subject: parsing tools, was What would early alternatives
At 12 Mar 2025 01:36:09 -0000, "John Levine" <johnl(a)taugh.com> wrote:
Subject: [TUHS] Re: parsing tools, was What would early alternatives
Lex was a dog. Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.
I've always understood the 'F' in Flex stood for "Fast". In fact
it
says as much right in the title of the manual page (right from the first
post to Usenet):
flex - fast lexical analyzer generator
--
Greg A. Woods <gwoods(a)acm.org>
Kelowna, BC +1 250 762-7675 RoboHack <woods(a)robohack.ca>
Planix, Inc. <woods(a)planix.com> Avoncote Farms <woods(a)avoncote.ca>
10 Mar
10 Mar
3:12 p.m.
New subject: What would early alternatives to C have been?
below... (At the risk of a case of being in disagreement with someone I
rarely am).
On Sun, Mar 9, 2025 at 10:03 PM Douglas McIlroy <
douglas.mcilroy(a)dartmouth.edu> wrote:
Yacc certainly makes it easier to write parsers for big grammars, but
it's far from cheating. You need to know a lot more about parsing to use
Yacc than you need to roll your own.
I disagree here. I have wtchged too many young programmers that I realized
did not understand what yacc was doing and came to understanding that
never built a simple parse before.
I'm not asking them to rebuild a parser for Algol68 or C++ in a one
semester course. I asking that to you take something like Dennis Allisons
"tiny basic" assignment for his Stanfrodf students in the lat 1970s and ask
them to build that.
Peter Hibbard gave us a super small Algol-ish language, and we generated
code for the "CMU Mini" (which was basically Gordon Bell's the precursor
to
the PDP-8 (see ISP below) - in my time the "Dragon Book was not yet written
BTW. I really understood what Stev had accomplished.
The interesting thing is while I tend to use yacc for most parsers, I've
found myself building recursive descent parsers in a couple of cases where
it seems to make better sense.
Hand parsing of a tiny grammar is almost a necessary step on the way to
understanding Yacc. But I think hand-building the whole parser for a
compiler is unnecessary torture--like doing trigonometry with log tables.
Point table ... however a funny thing to consider. My father was a high
school math teacher for 40 years. He noted that the loss of slide rules and
trig tables made his "modern" (post-calculator) students not understand
interpolation.To me, learning to use mathematical tables is a skill that
never hurts. I don't even think of asking people "to walk uphill both ways
to school in the snow and rain instead of riding a heated, dry yellow
school bus." I am asking the student to learn foundational ideas and build
skills up top of core understanding.
ᐧ
3:24 p.m.
New subject: What would early alternatives to C have been?
On Mon, Mar 10, 2025 at 11:13 AM Clem Cole <clemc(a)ccc.com> wrote:
On Sun, Mar 9, 2025 at 10:03 PM Douglas McIlroy
<douglas.mcilroy(a)dartmouth.edu> wrote:
Funny, I agree with both of you, and with Rob. :-)
If I'm not mistaken, I think what Doug was suggesting was that, to
really understand what YACC is _doing_ requires understanding a lot
more about the theory of parsing, grammars, and so on, than one needs
to understand to write a fairly simple RD parser. RD makes a lot of
sense intuitively, but once you introduce table-driven parsing,
LALR(1), etc, you get into a whole different level of theory and
rigor. Of course, by design the tool abstracts that away from you, so
to just _use_ it you don't necessarily need to understand as much.
Yacc certainly makes it easier to write parsers
for big grammars, but it's far from cheating. You need to know a lot more about
parsing to use Yacc than you need to roll your own.
I disagree here. I have wtchged too many young programmers that I realized did not
understand what yacc was doing and came to understanding that never built a simple parse
before. [...]
The interesting thing is while I tend to use yacc for most parsers, I've found
myself building recursive descent parsers in a couple of cases where it seems to make
better sense.
Funny, I'm the opposite: I've used YACC for a few parsers, but prefer
to roll my own. I find that I'm either parsing something very simple,
in which case reaching for YACC feels like cutting butter with a
chainsaw, or I need to do something that YACC isn't super great at
(like run in a multithreaded environment). YACC is superb at what it
does, but not something I feel like I need that often.
- Dan C.
11
days inactive
13
days old
20 comments
15 participants
participants (15)
-
Bakul Shah -
Charles H. Sauer -
Clem Cole -
Dan Cross -
Dave Horsfall -
Douglas McIlroy -
Greg A. Woods -
John Cowan -
John Levine -
John R Levine
-
Ken Thompson -
Larry McVoy -
Marc Rochkind -
Rich Salz -
Rob Pike