bit cleaner/consistent version:
Category/automata/lambda theory & discrete math provide human terminology for this. To keep things simple, intermediate data storage is not directly discussed (aka stack/heap) For this article, intermediate data storage just magically happens for this article. grammar referenced: https://pubs.opengroup.org/onlinepubs/9699919799.2018edition...
Going to try to keep things "abstract", as parse through tokens.
Each grammar to the right of the ":", "|" or "=" denotes how to arrive at a single token, the value to the left of ":","|" or "=". This is commonly referred to as the "l-value".
example grammar statement, program is the l-value.
program : linebreak
So, need to figure out the smallest group of tokens that define the r-value needed to create the l-value of a given grammar line/statement. Note: Grammar statement lays out order to fetch/perform operations to arrive at single token/l-value. (aka (a + b) -> get a value, get b value, get (a + b) value. So if ‘+’ is union, a & b are strings, the end result is the union of string a and union of string b.
grammar terminal l-value : token that can not be reduced further, terminal token (e.g. digit, character, reserved word, literal value).
Grammar non-terminal l-value : set of one or more l-values and how to get a single l-value out of this grammar instruction.
Getting back to the original question:
One throwback, somewhat less abstract way to visualize this is using "punch cards" (maps to function calls, returns only one token/value, "the l-value").
terminal punch cards hold terminal l-value token (character a, numeric value, literal character word, reserved words) Keeping things simple, non-terminal punch cards hold one combination of tokens (terminal/non-terminal) which show what to do with the token(s) listed on the “punch card” to get a single token/value to return. So, tokens wind up being references to other "punch cards" (terminal -> return card value, non-terminal -> go do other "punch cards", combine the values of other punch cards to determine the "l-value” result to return)
Basic parse pattern for each token(s)/r-values read-in, convert to grammar l-value. Note: May read-in many token(s)/r-values to arrive at single l-value. e.g. read in as many digits until get a non-digit & return the number/set of digits.
So, structures available to arrange "punch cards"/store the grammar r-values/l-values being parsed:
a) “punch cards” arranged as a linear array (traditionally, numerical index, but can be hashmap/named.) Advantage: straight forward linear traversal. Disadvantage: multiple copies of same index card, as no way to reference “repeated code”. Current “punch card” l-value is combined with result from next “punch card” array element. Repeat until single l-value at end of program.
b) variation on this is "dispatch table" aka switch/case statement, where the "punch card" l-value determines which switch/case statement to do next. Runtime traversals are modifiable, non-linear, and allow for shared, common l-values/”punch cards”
c) combine d & c via calls to functional array/list of ”named” punch-card references. Aka jump table, where the “punch card” l-value is index of the “punch card” to do next. Runtime traversals can be modified, non-linear, allow for shared common l-values, but also permit extending/additional l-values at run-time.
d) order "punch cards" as an abstract syntax tree (which if completely a math expression, change parse order to get infix, postfix, suffix traversals). Parse Tree nodes to call/evaluate the corresponding l-value grammar (function/function array reference). Easy name spaces, as each name space can be it’s own parse tree! Traversals can be “walked/rolled back” via tree walking/traversal.
no need to worry about exceeding array length, "array index" is implicit in parse, don't have to worry about "growing" array to insert token(s) within array.
e) recursive decent parser (each "punch card" is a function referencing next l-value(s)/punch card”(s) to call) – resource intensive, as intermediate values (stack/heap) provided by OS. Grammar determines parse order.