10
$\begingroup$

I'm designing a language that looks like this:

to kiss (a: a animal) passionately:
    say "you kiss" a.

to kiss the frog passionately:
    say "the frog turns into a princess".

the frog is a animal;
kiss the frog passionately.

This would print "the frog turns into a princess". While both variations of the function are valid, the more specific one is preferred.

This language is intended to be beginner friendly and specifically used by children.

Note that functions can get a lot more complex with multiple arguments, consider this function:

to attack (enemy: an enemy) with (weapon: a weapon):
    subtract the weapons damage from the enemys health // missspelling is intentional, language just inserts s for possessive with no regard for proper English grammar

the blue orc is a enemy
the blue orc has 5 health
the sword is a weapon
the sword has has 3 damage
attack the blue orc with the sword
say "The blue orc now has " the health of the blue orc "health";

What techniques can I use to parse code like this? Seems a normal context-free grammar, or even a extended grammar wouldn't be able to handle this.

I want help specifically for parsing calls to user generated function, I can manage the normal statements myself, or will ask a separate question for them when I get stuck.

$\endgroup$
8
  • 5
    $\begingroup$ The syntax feels a bit similar to ORK; maybe you could draw some inspiration from there. $\endgroup$
    – DLosc
    Commented May 20, 2023 at 19:47
  • $\begingroup$ You can see the JS source code of ORK here. It just parses everything with regex: formauri.es/personal/pgimeno/temp/esoteric/ork/… $\endgroup$
    – naffetS
    Commented May 20, 2023 at 19:48
  • $\begingroup$ Give ChatGPT instructions and feed the source code into it :P $\endgroup$
    – naffetS
    Commented May 20, 2023 at 20:26
  • $\begingroup$ In the title, can you please disambiguate "sentences"? "english sentences"? "human language sentences"? $\endgroup$
    – starball
    Commented May 20, 2023 at 21:08
  • $\begingroup$ @starball the main point is that they are multiple words, they are not really english sentences since they follow a strictly defined structure that happens to look like english $\endgroup$
    – mousetail
    Commented May 21, 2023 at 5:26

1 Answer 1

9
$\begingroup$

In a broad sense, these are mixfix function names: multiple-word names with arguments interspersed. They are not very common, but found most: famously in: Smalltalk, and also in Grace, where I got my experience with them. For context, here is a definition of your more complex example in Grace:

method attack (enemy: Enemy) with (weapon: Weapon) {
    subtract(weapon.damage) from (enemy.health)
}

That language requires parentheses around non-literal arguments, but this isn't strictly required to parse as long as you can tell where the argument expression stops. In this example you shouldn't have any trouble with that, but we'll come back to blue orc later.

There are two parsers I'll discuss: a hand-rolled recursive descent parser I wrote, and a parser-combinator one by someone else. There was also a Spoofax implementation that used an SDF3 grammar, but I can't speak to it. All of them should accept the same syntax as far as this goes, so methodology is not vastly important.

The parser code for something like that expression:

  1. Expects to have seen an identifier token to the left.
  2. Parses the arguments for this part: either a self-delimiting literal (1, "string") or a parenthesised list. This is where things get slightly more complex for you.
  3. Looks ahead for a further identifier token immediately following the arguments: if so, repeat, accumulating all name parts and arguments.
  4. Return the collected list of (name, argument list) pairs, and collate all the name parts together to identify the method in use in the same way that the declaration did.

The combinator version just does the same thing declaratively: firstArgumentHeader ~ repsep(argumentHeader,opt(ws)), which shouldn't be a problem in most kinds of grammar. In both cases this is an eager consumption because two terms in a row are not legal, which seems to be the case in your version as well.


You have two complications, both in the argument lists. One is in kiss the frog passionately, in that there's no argument list after passionately, which this algorithm would reject. This shouldn't be any trouble to fix in itself.

The other is in attack the blue orc with the sword. Presumably the is treated as a keyword and handled, but blue orc is still two words and we need to know to take them together and not expect a function attack...orc...sword. There are a few possible cases here, depending on what else the language does:

  • Most straightforwardly, we just know which identifiers have been created already and can peek ahead to take a full identifier if it's present. This can also operate for functions like the kiss the frog passionately overload.
  • It may be that every argument will always start with the, and so we just continue until the word that precedes that. This also falls over on the passionately case, but otherwise aligns with the Smalltalk :. The declaration of kiss the frog passionately would also recognise a parameter slot in the middle in this case.
  • There may be a concept of adjectives as prefixes such that blue still requires a noun afterwards and is consumed as part of a single term.
  • More awkwardly, you can generate multiple candidate parses and reject those that don't pan out. From the examples so far, these should uniquely disambiguate once names in scope are known.

I'm not sure which path will be right for this language, but it shouldn't present a major obstacle. It just needs to be dealt with somehow. The multi-word possessives should not be an issue, since you can tell that there is more to come, only multi-word heads of phrase.

The kiss the frog passionately overload of kiss (animal) passionately can be handled with multiple dispatch after parsing, and doesn't have to be addressed at this stage.


There aren't any in your example, but I'll note that one place where a problem does arise (and why Grace ended up with the parentheses) is when a multi-part function call can be an argument expression to another multi-part function: something like nearest...to in attack nearest enemy to me with the sword is difficult to parse without further indications.

$\endgroup$

You must log in to answer this question.

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