4
$\begingroup$

I have been working on a standard for a simple stack based language for a few weeks now. It has an extremely simple syntax.

" world!" "Hello," + .

Outputs Hello, world!.
For this language, would it make sense to create a parser, or should I just make a simple program that splits it up by spaces and executes it like that?

$\endgroup$
8
  • 1
    $\begingroup$ What is splitting up by spaces if not just very simple parsing? $\endgroup$
    – RubenVerg
    Jun 30, 2023 at 20:45
  • $\begingroup$ @RubenVerg Because "parsing" implies creating an AST. $\endgroup$ Jun 30, 2023 at 20:46
  • $\begingroup$ and what is a list of strings if not a very simple AST? $\endgroup$
    – RubenVerg
    Jun 30, 2023 at 20:48
  • $\begingroup$ @RubenVerg with that logic what is the output of a Lexer if not a simple AST? $\endgroup$ Jun 30, 2023 at 20:52
  • 2
    $\begingroup$ @Barmar Lists are trees where each node has at most one child. $\endgroup$
    – Abigail
    Jul 1, 2023 at 5:39

2 Answers 2

9
$\begingroup$

For a language that has entirely trivial syntax, just splitting by spaces is a parser, and that’s fine. Concatenative languages with only number literals can be one case of that, for example.

It doesn’t look like your language is quite that, however: your example contains a space within the first quoted string! Splitting by spaces will break that apart, and while you can repair it, the work to do so and future-proofing would point me towards making a simple parser, personally. Here the parser really is essentially a lexer, but it will address keeping quoted strings as single terms, perhaps escapes, etc.


If you’re going to have even slightly more complex syntax — like quotes or function literals — you’ll probably need a real parser. Those are very common to enable things like conditionals; sometimes a “jump to last [“ suffices, but only in the very simple cases.

Any sort of structure or nesting brings that into play, so while for the very early stages of implementation you can probably get away without one, it’s likely you’ll have to make one eventually. If the language really is just a linear front-to-back model perhaps you escape that.

$\endgroup$
2
  • 1
    $\begingroup$ Wouldn't this be more of a lexer than a real parser? $\endgroup$
    – Barmar
    Jun 30, 2023 at 21:32
  • 6
    $\begingroup$ @Barmar Really, a lexer is a type of simple parser in the most general sense of the word “parser”. By convention, when a language uses a lexer, we use the word “parser” to refer to the secondary parsing step that comes after lexing. But if there is no such division of labor, the distinction isn’t very useful. $\endgroup$
    – Alexis King
    Jun 30, 2023 at 21:50
5
$\begingroup$

I implemented a "simple" stack-based language (Unix dc) using a stack-based interpreter. I basically had the exact perfect situation to avoid a parser.

I wrote a parser anyway. In fact I also wrote a lexer.

So I suggest you at least write a parser.

Here's why: your language will not have just stack operations; it will also have things like storing into variables (you don't know how much you want this until you don't have it), and if your language is Turing-complete, you also need a way to jump forwards and backwards.

Yes, you can implement this with stack operations (push a string and use that as the variable name, or do math on the current program counter location prior to a jump), but I think you will probably want an easier method eventually.

And when you do, I think you will be grateful for your parser.

$\endgroup$
1
  • 1
    $\begingroup$ I've done something very similar: an experimental notation that broke expressions up into a tree with lots of ad-hoc rules rather than an explicit parser... and regretted it. My conclusion was that if a notation isn't amenable to being handled by a simple and efficient parser, then there's something wrong with it. $\endgroup$ Jul 1, 2023 at 6:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .