6 ms·

A BNF Parser in Forth (1992)

78 points by akkartik 7y ago

dvdkhlng 7y ago
There's another parser generator written in Forth, that I have personally used myself: Gray [1-3] The zip file [1] has english documentation, the papers [2,3] are unfortunately only available in german. This [4] is a mostly working grammar for the Verilog language written using Gray. It uses a lexer that sits on top of Gforth's regexp [5] package that directly compiles regexps into forth code (BTW quite a few bugs in the regexp package were triggered by the lexer and subsequently fixed upstream). [1] http://www.complang.tuwien.ac.at/forth/gray4.zip http://www.complang.tuwien.ac.at/forth/gray4.zip [2] http://www.complang.tuwien.ac.at/papers/ertl89.ps.gz http://www.complang.tuwien.ac.at/papers/ertl89.ps.gz [3] http://www.complang.tuwien.ac.at/papers/ertl97.ps.gz http://www.complang.tuwien.ac.at/papers/ertl97.ps.gz [4] https://sourceforge.net/p/fourhdl/code/HEAD/tree/trunk/parser.fs https://sourceforge.net/p/fourhdl/code/HEAD/tree/trunk/parse... [5] https://github.com/forthy42/gforth/blob/master/regexp.fs https://github.com/forthy42/gforth/blob/master/regexp.fs
- siraben 7y ago
  Here's a toy parser generator I wrote that works for context-free languages[0]. [0] https://github.com/siraben/meta-yacc https://github.com/siraben/meta-yacc
DonHopkins 7y ago
Oh wow, that's old school, and brings me back. I haven't thought of "SMUDGE" in a long time! One thing I love about FORTH is how completely off-the-wall and arbitrary some of the words are, even weirder than LISP's CAR and CDR. Most modern FORTH don't have SMUDGE any more, which has been replaced by HIDE and REVEAL. Perl programmers may savor and fetishize their weird arbitrary unreadable code like letter-sparse sigil-saturated line noise, but Perl can't hold a candle to the subtle beauty and enigmatically punctuated surrealistic symmetry of FORTH code: 8 : BNF: [COMPILE] : SMUDGE COMPILE <BNF ; IMMEDIATE 9 : ;BNF COMPILE BNF> SMUDGE [COMPILE] ; ; IMMEDIATE >b) Line 9 shows a recursive production, <S>. During the definition of a production, its name is automatically unSMUDGEd. Of course it's still possible to write self documenting FORTH code: : C(-; LICK SMILE NOSE WINK ; comp.lang.forth: Why smudge? https://groups.google.com/forum/#!topic/comp.lang.forth/olO-VHXJa1Q%5B1-25%5D https://groups.google.com/forum/#!topic/comp.lang.forth/olO-... >Does "smudge" have any other use than to stop the current word being found during a dictionary lookup? If not, then its only use would seem to be to allow a word to be defined in terms of another (older) word with the same name. Are there some useful things that can be done with this ability that make up for the (minor) extra complication? My other favorite (and much more useful and powerful for metaprogramming) FORTH words are <BUILDS and DOES>, but <BUILDS has been replaced by CREATE now, so they don't look as cool when used together. http://amforth.sourceforge.net/TG/recipes/Builds.html http://amforth.sourceforge.net/TG/recipes/Builds.html <BUILDS is the older sibling of CREATE. It has been in use in pre-ANSI Forth’s and is still around as an supplemental tool. It is a parsing word that takes the next word from the input source and creates a dictionary entry in the current word list. Unlike CREATE it does not add an execution token. Thus the word list entry created is unfinished and calling it will crash the system. The definition of the word list entry is finished with the DOES> section, that makes the word list entry a proper callable word. The big advantage over CREATE is that CREATE requires a rewrite of the contents of the execution token. That is on microcontrollers with the flash based dictionary only possible if a single cell can be re-programmed. The Atmegas can do that with little efforts, the MSP430 lacks essential ressources to do so. From the programming perspective there are no differences. <BUILDS can safely replace CREATE in defining words that contain a DOES> section as well. All other occurances of CREATE should remain unchanged. : constant create , does> @i ; \ or : constant <builds , does> @i ;
- dvdkhlng 7y ago
  > Most modern FORTH don't have SMUDGE any more, which has been replaced by HIDE and REVEAL. I think, the modern Forths (i.e. since 1994 ANS Forth standard) need neither HIDE nor REVEAL as these are made superflous by RECURSE. Other edge cases could be handled using a mechanism like DEFER [1] (which can be implemented in terms of ANS Standard words). Just looking through the manual, even the modern Gforth has something like RECURSIVE [2] which is just a differently named implementation of REVEAL. [1] http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Deferred-Words.html http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Defe... https://forth-standard.org/standard/core/RECURSE https://forth-standard.org/standard/core/RECURSE [2] http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Calls-and-returns.html#Calls-and-returns http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Call...
  - DonHopkins 7y ago
    One thing I love about SMUDGE is that SMUDGING again undoes the effect. If only that worked for my glasses. DEFER is great! But the word that resolves it should have been named REFED.
DonHopkins 7y ago
Here's a FORTH program to simulate a 7 bit paper tape puncher. Type PTAPE <cr> and then start typing. It will terminate and cut the tape when you type a <null>. \ FORTH PAPER TAPE PUNCHER: : PT# ( L --- L/2 ) DUP 1 AND IF ASCII @ ELSE BL THEN HOLD 2/ ; : PT. ( N --- ) <# PT# PT# PT# ASCII . HOLD PT# PT# PT# PT# #> TYPE ; : CUT ." -----------" CR ; : PTAPE CUT BEGIN KEY ?DUP WHILE DUP ." |" PT. ." |" SPACE EMIT CR REPEAT CUT ; PS: I rewrote PTAPE in PostScript for NeWS, so it makes a window with actual holes punched into it in the shape of a piece of paper tape with the text you pass in as a parameter: https://www.donhopkins.com/home/archive/news-tape/fun/ptape/ptape https://www.donhopkins.com/home/archive/news-tape/fun/ptape/... Can anybody write that for X11 using the SHAPES extension to punch the holes in fewer lines of code? ;) (The comments about an elliptical canvas and round shape must have been copied from some other old code, because the shape of the window (and icon) it makes is rectangular with lots of round holes punched into it.)
ChrisMarshallNY 7y ago
Argh. BNF. I had enough of that to last me a lifetime by 1986 (I used to do X.400 stuff). That said, it’s pretty cool.
java-man 7y ago
When I coded a Forth virtual machine in 8080 assembly in 1985, I soon realized Forth is a write-only language. Fun, but totally unusable for a mediocre programmer like myself.
- haolez 7y ago
  It has less syntax than any other language and it's very good for making a thin DSL layer above your hardware. Please share your experience on this :)
  - java-man 7y ago
    Granted, I was just a kid back then. Read a book about Forth, thought this was an ideal language to write a vm given very limited resources of my home build computer (1K of static RAM). Wrote it in assembly (on a sheet of paper, compiled to hex by hand). Then I tried to write a function that prints a number in decimal format, and realized I could not debug it. Fail!
  - anadem 7y ago
    "My" FORTH was done in 6502 assembler, and used for a water company records and billing system which included interfaces for the company to get the local water flow rates! The meters reported with synthetic voices. Back then BT owned the phone system and were very resistant to letting us pass data from the flow meters to the head office: was it voice or was it data? We argued over that for weeks.
    - java-man 7y ago
      I am almost afraid to ask: is it still in operation? Some of these systems are kept for surprisingly long time (don't fix if it ain't broken)

78 points by akkartik 7y ago

There's another parser generator written in Forth, that I have personally used myself: Gray [1-3] The zip file [1] has english documentation, the papers [2,3] are unfortunately only available in german. This [4] is a mostly working grammar for the Verilog language written using Gray. It uses a lexer that sits on top of Gforth's regexp [5] package that directly compiles regexps into forth code (BTW quite a few bugs in the regexp package were triggered by the lexer and subsequently fixed upstream). [1] http://www.complang.tuwien.ac.at/forth/gray4.zip http://www.complang.tuwien.ac.at/forth/gray4.zip [2] http://www.complang.tuwien.ac.at/papers/ertl89.ps.gz http://www.complang.tuwien.ac.at/papers/ertl89.ps.gz [3] http://www.complang.tuwien.ac.at/papers/ertl97.ps.gz http://www.complang.tuwien.ac.at/papers/ertl97.ps.gz [4] https://sourceforge.net/p/fourhdl/code/HEAD/tree/trunk/parser.fs https://sourceforge.net/p/fourhdl/code/HEAD/tree/trunk/parse... [5] https://github.com/forthy42/gforth/blob/master/regexp.fs https://github.com/forthy42/gforth/blob/master/regexp.fs

siraben 7y ago
Here's a toy parser generator I wrote that works for context-free languages[0]. [0] https://github.com/siraben/meta-yacc https://github.com/siraben/meta-yacc

DonHopkins 7y ago

Oh wow, that's old school, and brings me back. I haven't thought of "SMUDGE" in a long time! One thing I love about FORTH is how completely off-the-wall and arbitrary some of the words are, even weirder than LISP's CAR and CDR. Most modern FORTH don't have SMUDGE any more, which has been replaced by HIDE and REVEAL. Perl programmers may savor and fetishize their weird arbitrary unreadable code like letter-sparse sigil-saturated line noise, but Perl can't hold a candle to the subtle beauty and enigmatically punctuated surrealistic symmetry of FORTH code: 8 : BNF: [COMPILE] : SMUDGE COMPILE <BNF ; IMMEDIATE 9 : ;BNF COMPILE BNF> SMUDGE [COMPILE] ; ; IMMEDIATE >b) Line 9 shows a recursive production, <S>. During the definition of a production, its name is automatically unSMUDGEd. Of course it's still possible to write self documenting FORTH code: : C(-; LICK SMILE NOSE WINK ; comp.lang.forth: Why smudge? https://groups.google.com/forum/#!topic/comp.lang.forth/olO-VHXJa1Q%5B1-25%5D https://groups.google.com/forum/#!topic/comp.lang.forth/olO-... >Does "smudge" have any other use than to stop the current word being found during a dictionary lookup? If not, then its only use would seem to be to allow a word to be defined in terms of another (older) word with the same name. Are there some useful things that can be done with this ability that make up for the (minor) extra complication? My other favorite (and much more useful and powerful for metaprogramming) FORTH words are <BUILDS and DOES>, but <BUILDS has been replaced by CREATE now, so they don't look as cool when used together. http://amforth.sourceforge.net/TG/recipes/Builds.html http://amforth.sourceforge.net/TG/recipes/Builds.html <BUILDS is the older sibling of CREATE. It has been in use in pre-ANSI Forth’s and is still around as an supplemental tool. It is a parsing word that takes the next word from the input source and creates a dictionary entry in the current word list. Unlike CREATE it does not add an execution token. Thus the word list entry created is unfinished and calling it will crash the system. The definition of the word list entry is finished with the DOES> section, that makes the word list entry a proper callable word. The big advantage over CREATE is that CREATE requires a rewrite of the contents of the execution token. That is on microcontrollers with the flash based dictionary only possible if a single cell can be re-programmed. The Atmegas can do that with little efforts, the MSP430 lacks essential ressources to do so. From the programming perspective there are no differences. <BUILDS can safely replace CREATE in defining words that contain a DOES> section as well. All other occurances of CREATE should remain unchanged. : constant create , does> @i ; \ or : constant <builds , does> @i ;

dvdkhlng 7y ago
> Most modern FORTH don't have SMUDGE any more, which has been replaced by HIDE and REVEAL. I think, the modern Forths (i.e. since 1994 ANS Forth standard) need neither HIDE nor REVEAL as these are made superflous by RECURSE. Other edge cases could be handled using a mechanism like DEFER [1] (which can be implemented in terms of ANS Standard words). Just looking through the manual, even the modern Gforth has something like RECURSIVE [2] which is just a differently named implementation of REVEAL. [1] http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Deferred-Words.html http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Defe... https://forth-standard.org/standard/core/RECURSE https://forth-standard.org/standard/core/RECURSE [2] http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Calls-and-returns.html#Calls-and-returns http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Call...
- DonHopkins 7y ago
  One thing I love about SMUDGE is that SMUDGING again undoes the effect. If only that worked for my glasses. DEFER is great! But the word that resolves it should have been named REFED.

DonHopkins 7y ago

Here's a FORTH program to simulate a 7 bit paper tape puncher. Type PTAPE <cr> and then start typing. It will terminate and cut the tape when you type a <null>. \ FORTH PAPER TAPE PUNCHER: : PT# ( L --- L/2 ) DUP 1 AND IF ASCII @ ELSE BL THEN HOLD 2/ ; : PT. ( N --- ) <# PT# PT# PT# ASCII . HOLD PT# PT# PT# PT# #> TYPE ; : CUT ." -----------" CR ; : PTAPE CUT BEGIN KEY ?DUP WHILE DUP ." |" PT. ." |" SPACE EMIT CR REPEAT CUT ; PS: I rewrote PTAPE in PostScript for NeWS, so it makes a window with actual holes punched into it in the shape of a piece of paper tape with the text you pass in as a parameter: https://www.donhopkins.com/home/archive/news-tape/fun/ptape/ptape https://www.donhopkins.com/home/archive/news-tape/fun/ptape/... Can anybody write that for X11 using the SHAPES extension to punch the holes in fewer lines of code? ;) (The comments about an elliptical canvas and round shape must have been copied from some other old code, because the shape of the window (and icon) it makes is rectangular with lots of round holes punched into it.)

ChrisMarshallNY 7y ago

Argh. BNF. I had enough of that to last me a lifetime by 1986 (I used to do X.400 stuff). That said, it’s pretty cool.

java-man 7y ago

When I coded a Forth virtual machine in 8080 assembly in 1985, I soon realized Forth is a write-only language. Fun, but totally unusable for a mediocre programmer like myself.

haolez 7y ago
It has less syntax than any other language and it's very good for making a thin DSL layer above your hardware. Please share your experience on this :)
- java-man 7y ago
  Granted, I was just a kid back then. Read a book about Forth, thought this was an ideal language to write a vm given very limited resources of my home build computer (1K of static RAM). Wrote it in assembly (on a sheet of paper, compiled to hex by hand). Then I tried to write a function that prints a number in decimal format, and realized I could not debug it. Fail!
- anadem 7y ago
  "My" FORTH was done in 6502 assembler, and used for a water company records and billing system which included interfaces for the company to get the local water flow rates! The meters reported with synthetic voices. Back then BT owned the phone system and were very resistant to letting us pass data from the flow meters to the head office: was it voice or was it data? We argued over that for weeks.
  - java-man 7y ago
    I am almost afraid to ask: is it still in operation? Some of these systems are kept for surprisingly long time (don't fix if it ain't broken)