14

I've recently undertaken the task of writing a stack-based programming language. Before I started designing my language however, I thought it'd be a good idea to read and experiment with existing stack-based languages.

This brings me to the topic of this post. I was reading through the Wikipedia article on Forth, a stack-based language which uses postfix style expressions. In the article, I saw the following statement:

Forth's flexibility makes a static BNF grammar inappropriate, and it does not have a monolithic compiler. Extending the compiler only requires writing a new word, instead of modifying a grammar and changing the underlying implementation.

From my understanding, in Forth lingo, the term "word" seems to be basically synonymous with "subroutine". Given this, the above statement seems strange. Why exactly would the ability to create new functions in Forth make a formal grammar for Forth inappropriate? Why would you need to re-write the grammar for each new subroutine you define? How does writing a new word in the environment constitute extending the compiler? The above statement seems akin to saying that a formal grammar is inappropriate for Python because you can define new functions.

In fact,  I decided to attempt to write a BNF style grammar for a simple subset of Forth below:

program        ::= stmt+
stmt           ::= func | expr
func           ::= ':' expr+ ';'
expr           ::= INTEGER | word
word           ::= ('+' | '-' | '*' | '/' )

The above grammar would seem to cover a valid subset of Forth statements, and doesn't seem that hard to extended to cover all valid statements in the Forth language. Furthermore, if a compiler's parser implements the above grammar, I fail to see how the compiler would ever be extended. The compiler will simply add any new words to it's environment. Only the environment is changed. It almost seems as if the above excerpt from Wikipedia is conflating the underlining code that composes the compiler (which does not change) with the compiler's environment (which does change).

In summary,  why would Forth's ablitiy to define new words (subroutines) make is inappropriate for a written grammar?

4
  • 1
    "Inappropriate" is a strong word in this context. A better word would probably be "unnecessary." May 6, 2018 at 1:29
  • 1
    Oh, okay @RobertHarvery. However, if that were the case, then the excerpt I quoted would seem to apply to most languages. Technically a grammar is never needed, but it's nice to have one - especially when hand-writing parsers. May 6, 2018 at 2:02
  • 2
    But in most languages, the parser is not a simple runtime library that can be changed by user code, thus affecting how the next line is parsed. May 6, 2018 at 10:18
  • 1
    Most languages do significant work to limit & constrain the programmer, to give structure & rigidly-defined words/phrases/grammars. Forth instead empowers the developer to do what is needed. Forth has no reserved words, & allows you to redefine the entire language. This allows you to write an integrated debugger, or lightweight OOPS, or a strongly-typed FORTH, a BASIC or PASCAL interpreter, or a Scheme or Lisp. These are things I have actually seen being done in Forth. Of course, with more flexibility comes more risk, & more potential. FactorCode.org shows advanced ways I'd like Forth to take. Jan 18, 2021 at 0:21

3 Answers 3

13

A "normal" word is pretty much just a subroutine.

...but you can write a user-defined defining word, which change how the compiler works. For example, a definition normally starts with a colon (":") and ends with a semicolon (";"). But if you want, you can (for example) change what the colon does, and in the process change how a word definition is "compiled", thereby changing how the compiler works, and changing the grammar of the language being recognized.

This is why it's saying a grammar is inappropriate--the grammar can quite literally change from one part of the program to another. Loading a dictionary can change not only the subroutines whose names are currently recognized, but also the grammar that's parsed when you define a new word.

7
  • 2
    Are you sure this property of Forth really changes the grammar and not just the semantics?
    – Doc Brown
    May 6, 2018 at 13:39
  • @DocBrown: Most people who use Forth like it quite a lot, so they typically make only the most minimal changes necessary for the task at hand. Somebody who was ambitious (and crazy) enough could change the syntax completely if they wanted--like using infix notation instead of postfix, if they wanted to badly enough. May 6, 2018 at 15:21
  • @DocBrown What kind of grammar could you possibly write that would allow me to write a C interpreter in Forth, and then suddenly switch to C in the middle of the program?
    – user253751
    May 7, 2018 at 5:34
  • @immibis: well, my question is - does Forth really allow something like this? From that linked article, this is not inherently clear to me.
    – Doc Brown
    May 7, 2018 at 5:53
  • @DocBrown Yes it does. You can run your code at compile time, that means if you want to you can fully take over the compiler. Basically you can run your C compiler/interpreter in the middle of the Forth compiler/interpreter. (whether you want to eventually return back to Forth or not is up to you)
    – user253751
    May 7, 2018 at 5:55
6

In Forth, you can run code at compile time.

In particular, you can run code that consumes words from the input. For example, you could write a C compiler in Forth, and then call it at compile-time, and then write the rest of your program in C.

More commonly, you can define words that read arguments from the source code. Traditionally you would read words the same way the compiler does, but it's not required.

For instance, the ." word (which prints a string) does not read until the next space, it reads until the next ". If you try to parse the code : PRINTHELLO ." Hello ; : func2 world!" ; without a special case for .", you will find that it is not parsed correctly.

You can certainly add a special case for ." to your grammar, but the grammar will still be incorrect if the programmer defines their own word like ." - for example here's one: : MY_PRINT POSTPONE ." ; IMMEDIATE. This word is equivalent to ."; I can write MY_PRINT Hello ; world! " and your grammar needs to be able to parse it. Good luck with that.

3

A typical approach involving use of a BNF style grammar implies creation of some sort of tokenizer → parser → generator chain where grammar will be used by parser to form Abstract Syntax Tree from incoming stream of tokens. However such an approach is not viable for FORTH because it is a concatenative programming language. Tokenizing in FORTH is performed by splitting incoming symbols into words using whitespace and that's it. Each word is immediately executed one after another according to current state of the interpreter. They never form expressions, there is no AST to build. Meaning of words always depends on sequence of previously executed words.

For example in func ::= ':' expr+ ';' the words :, ; and all the words between them are executed separately, one by one, - : changes interpreter state so it will prepare to accept a word to be defined, and some more incoming words executing compilation semantics for each. Compilation semantics for ; is to finish executing compilation semantics and word definition. However technically any other word with equivalent semantics can be used instead of ; and such a word may receive them after : is executed - a scenario that can not be covered by grammar.

1
  • 1
    -1: the fact that Forth interpreters don't build ASTs does not imply that an AST can't be built anyway.
    – user253751
    Sep 17, 2021 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.