3 ms·

Category/autonoma/lambda theory & discrete math provide human terminology for this. To keep things simple, intermidiate data storage is not directly discussed (

Category/autonoma/lambda theory & discrete math provide human terminology for this. To keep things simple, intermidiate data storage is not directly discussed (aka stack/heap) For this artile, intermediate data storage just magically happens for this article. grammar referenced: https://pubs.opengroup.org/onlinepubs/9699919799.2018edition/utilities/V3_chap02.html#tag_18_10 https://pubs.opengroup.org/onlinepubs/9699919799.2018edition... Going to try to keep things "abstract", as parse through tokens. Each grammer to the right of the ":", "|" or "=" denotes how to arrive at a single token, the value to the left of ":","|" or "=". This is commonly refered to as the "l-value". example grammar statement, program is the l-value. program : linebreak need to figure out the smallest group of tokens needed to get the l-value of a grammer Note: Grammer lays out order to fetch/perform operations to arrive at single token, for a given grammer statement (withing a given grammer function) (aka (a + b) -> get a value, get b value, get (a + b) value terminal grammer l-value : token that can not be reduced further, terminal token. non-terminal l-value : set of one or more l-values and how to get a single l-value out of this grammer instruction. 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, numberic value, literal character word) Keeping things simple, non-terminal punch cards hold one combination of tokens (reducible/non-reduceable) with what to do with the token(s) 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") So, structuring the order to parse the tokens can be done by: a) assign numeric values to each of the grammer l-values (translate r-value tokens into l-value reference) when read in "shell script" changes each token/grammer l-value to corresponding shell grammer reference. identified group(s)/sets of token values are associated with a "punch card" index (array reference) when done, run through "punch card" index starting from each array index "calls" the associated "punch card" to process things. note: token/value returned from "punch card" is combined with result from next array element. when reach end of array, should have just one "token" value! b) variation on this is "dispatch table" aka switch statement, where the "punch card" return value determines which switch statement to do next. c) combine d & c via calls to functional array. function in function array to be called based on "punch card" return value. d) order "punch cards" as an abstract syntax tree (which if completely a math expression, change parse order to get infix, postfix, suffiex printouts) hashmap to call function in function array. 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)

sargstuff 5y ago
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 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.

sargstuff 5y ago

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 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.