10

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?

  • 1
    "Inappropriate" is a strong word in this context. A better word would probably be "unnecessary." – Robert Harvey May 6 '18 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. – Christian Dean May 6 '18 at 2:02
  • 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. – Jörg W Mittag May 6 '18 at 10:18
10

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.

  • 2
    Are you sure this property of Forth really changes the grammar and not just the semantics? – Doc Brown May 6 '18 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. – Jerry Coffin May 6 '18 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 '18 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 '18 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 '18 at 5:55
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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