5 ms·

A recursive descent parser in Forth

71 points by lizmat 7y ago

coldcode 7y ago
while the article seemed interesting, all the constant repeated ads (looking at work, no blocker) is horrible
- lizmat 7y ago
  This is weird. I don't see any ads on that page, and I don't have any ad-blockers. I am looking at it with Safari, so maybe that's the difference?
  - jhoechtl 7y ago
    Unlikely. You should see the items google thinks are relvant for you but 10% more expensive as you belong to a user group which spends money on items with little comparable advantage above others except being more expensive for the purpose to differentiate from others.
- aazaa 7y ago
  Some people just don't care enough about their content or brand to worry about the terrible experience they give users by plastering chum all over their pages in a ridiculous attempt to pick up pennies.
  - blippage 7y ago
    The blog is a free Wordpress one. Authors have no control over the ads shown, nor do they receive money from the ads that are displayed.
carapace 7y ago
He links to an awesome article: "A BNF PARSER IN FORTH" by Brad Rodriguez that "...first appeared in ACM SigFORTH Newsletter vol. 2 no. 2" https://www.bradrodriguez.com/papers/bnfparse.htm https://www.bradrodriguez.com/papers/bnfparse.htm Imagine getting your Forth firmware loaded with this in it, you can already do e.g. OMeta-style grammars because it's still Forth, so you can send your device a language description preamble and then just talk to it in whatever language you like, all in one stream. ( https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta )
- swiley 7y ago
  FORTH is pretty awesome and I love stack machines. After my experiences with postscript (and being a web user like everyone else) allowing for recursion when you don’t really need it freaks me out a little.
siraben 7y ago
META-II is a paper worth reading. I wrote a self-hosting parser generator in Forth based on that paper[0]. [0] https://github.com/siraben/meta-yacc/blob/master/meta.fs https://github.com/siraben/meta-yacc/blob/master/meta.fs
akkartik 7y ago
"we cannot create assembly code output from Meta II, as assemblers don’t allow for the inlining of strings." This is actually not a major limitation. We've just been blinkered by decades of one kind of notion for "Assembler". It's actually quite easy to create a syntax atop machine code (and implemented in machine code) that provides string literals. As evidence: I've done it. Here's the pass in my 'assembler' that implements string literals: http://akkartik.github.io/mu/html/apps/dquotes.subx.html http://akkartik.github.io/mu/html/apps/dquotes.subx.html. That page is 1925 lines long, but take out the comments and unit tests and there's only 383 lines of code (336 x86 instructions). Including library functions elsewhere (also built in machine code) the resulting binary is 6.5KB large. There's an example up top that I'll reproduce here: $ cat x == code ab "cd ef"/imm32 $ cat x | apps/dquotes == code ab __string1/imm32 == data __string1: 5/imm32/length 0x63/c 0x64/d 0x20/ 0x65/e 0x66/f All it's doing is moving string literals to the data segment and replacing their original location with the label they were moved to. Currently there's zero optimization; if you refer to "foo" 3 times you get 3 separate literals in your binary and data segment. More details on the syntax: http://akkartik.name/post/mu-2019-1 http://akkartik.name/post/mu-2019-1. HN discussion: https://news.ycombinator.com/item?id=21268252 https://news.ycombinator.com/item?id=21268252.
- Someone 7y ago
  The forth way of doing that is even simpler: - generate a call to a subroutine LITERAL - store the characters of the string directly after that call - pad to the ‘word’ size LITERAL does: - pop the return address from the call stack - from that address, compute the address of the literal - push it to Forth’s data stack - adjust the return address to point beyond the literal - push the adjusted return address - return from subroutine And of course, this being Forth, you can define such words yourself (https://www.forth.com/starting-forth/11-forth-compiler-defining-words/ https://www.forth.com/starting-forth/11-forth-compiler-defin... (an excellent site, by the way))
  - akkartik 7y ago
    For sure. I love Forth and spent a long time thinking about it [1]. I'm exploring some different trade-offs in my project, worse than Forth in some ways and hopefully better than Forth in others. [1] https://plforums.org/practice/minimal-features-required-for-an-extensible-language#post_65 https://plforums.org/practice/minimal-features-required-for-...

71 points by lizmat 7y ago

coldcode 7y ago

while the article seemed interesting, all the constant repeated ads (looking at work, no blocker) is horrible

lizmat 7y ago
This is weird. I don't see any ads on that page, and I don't have any ad-blockers. I am looking at it with Safari, so maybe that's the difference?
- jhoechtl 7y ago
  Unlikely. You should see the items google thinks are relvant for you but 10% more expensive as you belong to a user group which spends money on items with little comparable advantage above others except being more expensive for the purpose to differentiate from others.
aazaa 7y ago
Some people just don't care enough about their content or brand to worry about the terrible experience they give users by plastering chum all over their pages in a ridiculous attempt to pick up pennies.
- blippage 7y ago
  The blog is a free Wordpress one. Authors have no control over the ads shown, nor do they receive money from the ads that are displayed.

carapace 7y ago

He links to an awesome article: "A BNF PARSER IN FORTH" by Brad Rodriguez that "...first appeared in ACM SigFORTH Newsletter vol. 2 no. 2" https://www.bradrodriguez.com/papers/bnfparse.htm https://www.bradrodriguez.com/papers/bnfparse.htm Imagine getting your Forth firmware loaded with this in it, you can already do e.g. OMeta-style grammars because it's still Forth, so you can send your device a language description preamble and then just talk to it in whatever language you like, all in one stream. ( https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta )

swiley 7y ago
FORTH is pretty awesome and I love stack machines. After my experiences with postscript (and being a web user like everyone else) allowing for recursion when you don’t really need it freaks me out a little.

siraben 7y ago

META-II is a paper worth reading. I wrote a self-hosting parser generator in Forth based on that paper[0]. [0] https://github.com/siraben/meta-yacc/blob/master/meta.fs https://github.com/siraben/meta-yacc/blob/master/meta.fs

akkartik 7y ago

"we cannot create assembly code output from Meta II, as assemblers don’t allow for the inlining of strings." This is actually not a major limitation. We've just been blinkered by decades of one kind of notion for "Assembler". It's actually quite easy to create a syntax atop machine code (and implemented in machine code) that provides string literals. As evidence: I've done it. Here's the pass in my 'assembler' that implements string literals: http://akkartik.github.io/mu/html/apps/dquotes.subx.html http://akkartik.github.io/mu/html/apps/dquotes.subx.html. That page is 1925 lines long, but take out the comments and unit tests and there's only 383 lines of code (336 x86 instructions). Including library functions elsewhere (also built in machine code) the resulting binary is 6.5KB large. There's an example up top that I'll reproduce here: $ cat x == code ab "cd ef"/imm32 $ cat x | apps/dquotes == code ab __string1/imm32 == data __string1: 5/imm32/length 0x63/c 0x64/d 0x20/ 0x65/e 0x66/f All it's doing is moving string literals to the data segment and replacing their original location with the label they were moved to. Currently there's zero optimization; if you refer to "foo" 3 times you get 3 separate literals in your binary and data segment. More details on the syntax: http://akkartik.name/post/mu-2019-1 http://akkartik.name/post/mu-2019-1. HN discussion: https://news.ycombinator.com/item?id=21268252 https://news.ycombinator.com/item?id=21268252.

Someone 7y ago
The forth way of doing that is even simpler: - generate a call to a subroutine LITERAL - store the characters of the string directly after that call - pad to the ‘word’ size LITERAL does: - pop the return address from the call stack - from that address, compute the address of the literal - push it to Forth’s data stack - adjust the return address to point beyond the literal - push the adjusted return address - return from subroutine And of course, this being Forth, you can define such words yourself (https://www.forth.com/starting-forth/11-forth-compiler-defining-words/ https://www.forth.com/starting-forth/11-forth-compiler-defin... (an excellent site, by the way))
- akkartik 7y ago
  For sure. I love Forth and spent a long time thinking about it [1]. I'm exploring some different trade-offs in my project, worse than Forth in some ways and hopefully better than Forth in others. [1] https://plforums.org/practice/minimal-features-required-for-an-extensible-language#post_65 https://plforums.org/practice/minimal-features-required-for-...