Exploring how to define a Grammar in APL using BNF-like syntax

0-Readme.md

BNF in APL

Exploring how to define a Grammar in APL using BNF-like syntax

1-example_grammar.apl

⍝ Example Grammar:
      HELLO ← 'hello world'
      BYE ← 'bye world'
      CONVERSATION ← HELLO , ' and then ' , BYE

⍝ CAPITALIZED words are the non-terminals
⍝ 'Strings' are the terminals
⍝ Concatenation is done with ,

2-example_output.apl

⍝ Output:      
      HELLO
hello world
      BYE
bye world
      CONVERSATION
hello world and then bye world

Redefining non-terminals, makes everything a bit easier, since there a more correct mental mapping.

abstracting away for now the fact that terminals are strings with varying length:

• terminals are matrixes with the dimensions 1 × length, ie as many elements as the string's length.
• non-terminals are matrixes with the dimensions a × length, where:
  • a is the amount of "alternations" it has.
    By alternations we mean the amount if alternative terminals it can derive to.
  • and length is the length of its longest string

---

if we concatenate:

• two terminals we get a matrix with the dimensions 1 × (length of terminal 1 + length of terminal 2)
• a terminal and a non-terminal we get a matrix with the dimensions a × (length of non-terminal + length of terminal)
• two non-terminals we get a matrix with the dimensions a' × length', where:
  • length' = length of non-terminal 1 + length of non-terminal 2
  • a' = alternations (a) of non-terminal 1 × alternations (a) of non-terminal 2

---

if you think about it, this is a much better distinction between non-terminals and terminals compared to;

'hello world'          ⍝ this is a terminal
HELLO ← 'hello world'  ⍝ this is a non-terminal

⍝ yes I know I'm being facetious,
⍝ here's perhaps a more fair representation of the standard definition, but its still pretty bad:

'this is a terminal'                 ⍝  this is a terminal
non-terminal ← 'this is a terminal'  ⍝  this is a terminal being assign to a non-terminal

          HELLO ←  ⍪ 'hello world' 'hey world'
      HELLO
┌───────────┐
│hello world│
├───────────┤
│hey world  │
└───────────┘
          BYE ← ⍪ 'bye world' 'cya world'
      BYE
┌─────────┐
│bye world│
├─────────┤
│cya world│
└─────────┘
          ]display ⍪, (HELLO ∘., BYE)
┌→───────────────────────┐
↓ ┌→───────────────────┐ │
│ │hello worldbye world│ │
│ └────────────────────┘ │
│ ┌→───────────────────┐ │
│ │hello worldcya world│ │
│ └────────────────────┘ │
│ ┌→─────────────────┐   │
│ │hey worldbye world│   │
│ └──────────────────┘   │
│ ┌→─────────────────┐   │
│ │hey worldcya world│   │
│ └──────────────────┘   │
└∊───────────────────────┘
          (⊂ 'hey world ') ∘., (⊂ 'cya world')
┌───────────────────┐
│hey world cya world│
└───────────────────┘