5 ms·

What is the best way to parse shell-like syntax without a lexer?

2 points by cassepipe 5y ago

Hi HN ! I would like to build a shell syntax parser and I would like to do it without yacc or tools like that, for learning purposes. I have been reading a lot parsing tutorials and I got a tokenizer working. From what I have read I now either have to make a parse tree or an abstract syntax tree out of my tokens with the help of a grammar from this page [1] Now can you point me to any good documentation on how to make a tree out of it ? All the tutorials I could find on the matter are made for arithmetic syntax and somehow I haven't been able to adapt those to my use case. I have also read article from the creator of Oil shell and talks about how making a modal tokenizer would make sense for the shell syntax but I have not been able to find anything on how to build such a thing. Have ever done one ? [1] https://pubs.opengroup.org/onlinepubs/9699919799.2018edition/utilities/V3_chap02.html#tag_18_10

trinovantes 5y ago
In my experience, the easiest way to understand/implement a parser is with a recursive descent parser https://en.wikipedia.org/wiki/Recursive_descent_parser https://en.wikipedia.org/wiki/Recursive_descent_parser
bediger4000 5y ago
You could take a look at how the "heirloom bourne shell" does it: http://heirloom.sourceforge.net/sh.html http://heirloom.sourceforge.net/sh.html
- sargstuff 5y ago
  check out how morbig uses a shell grammar to parse a shell script in order to build a syntax tree. https://news.ycombinator.com/item?id=30812330 https://news.ycombinator.com/item?id=30812330 Technically, it's not lexx && slightly different shell grammar than [1]. Can feed in grammar based on [1] and/or make grammar changs and see how morbig generates the syntax tree.
  - sargstuff 5y ago
    Tree-sitter : https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/ From the tree-sitter website: "Tree-sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and efficiently update the syntax tree as the source file is edited."
rurban 5y ago
PEG or rec descent
sargstuff 5y ago
How do I build a grammar tree is akin to saying how is a language read. Grammar tree, like language depends on what grammar is read. e.g. japanese grammar handled bit differently than english grammar The wierd thing about [1] is the grammer symbols section rules do not define 100% of valid lexical tokens. Where tokens are implied in grammer symbols section, see relevant rules section. If have tokenized things, then just need to used/read in token(s), search grammar rule tree till find terminal token that matches lvalue, then return to priror level & complete rest of grammar rule, etc.. until get back up to top of tree. shell example: variable = "asdf" Do an in order traversl to parse grammar. (recursive desent will make remembering where at & moving back up grammar tree bit easier -- function call will retain how much of grammar rule have done at a given tree level) To set a variable, recursively walk through grammar lvalue rules array/tree and evaluating the rvalues in the lvalue rules until current token matches an lvalue rule. aka grammar rules 1st lvalue in tree is program. Example walkthrough of shell program variable = "asdf" 1) tokenizing variable = "asdf" gives 1st l_value token is WORD_ASSIGNMENT WORD_ASSIGNMENT has the value -> variable 2rd l_value token is WORD WORD has a value -> "asdf" 3nd l_value token is NEWLINE 2) grammar tree walk notation: (lvalue) means, doing next set of rvalues (bump in indentation) if (lvalue) isn't before "->" means rvalue of an lvalue rule in 1st line above it that include (lvalue). Grammar tree rules walkthrough trace. (top of tree is PROGRAM rule): program (lvalue)-> linebreak(lvalue) -> /*empty*/ complete_commands (lvalue)-> complete_commands -> nomatch newline_list -> no match complete_command(lvalue) -> list(lvalue) -> list-> no match seperator_op -> no_match and_or -> no match linebreak -> /*empty*/ Note: have reached the end of the lvalue "program", so have all the 'rvalues" needed to generate the program lvalue. apply section 2.10.1, 'WORD_ASSIGNMENT' (tokenizer should have recognized WORD before =), generate a storage location for the variable name contained in WORD_ASSIGNMENT token. if next fetched token is WORD, then assign store value of WORD token to WORD_ASSIGNMENT variable.
sargstuff 5y ago
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
Parsing shell-like syntax using turning complete excel to be able to parse shell-like syntax is step up from asci programming, but certainly drives home why would want to use a lexer. IMHO, Fortran language implienter has nicer real world experience on why would want to use things like lex/yacc. Suggest grouping associate shell command to excel function name that calls the turning tape that does the requested shell command (perhaps one excell spreadsheet per turning tape?). aka turing shell recursive decent parser. https://www.felienne.com/archives/2974 https://www.felienne.com/archives/2974 && https://www.microsoft.com/en-us/research/blog/lambda-the-ultimatae-excel-worksheet-function/ https://www.microsoft.com/en-us/research/blog/lambda-the-ult... Although, IMHO, might want to upgrade the turning complete excel stuff to support a less verbose grammer type 1 or type 2 first.
- sargstuff 5y ago
  Call it the 'irate' programming language implimented in excel. Milage may vary on if 'excel - irate' actually does what's intended.
sargstuff 5y ago
Universal parser: Simplest possible parse exercise: https://morphett.info/turing/turing.html https://morphett.info/turing/turing.html recursive functions to turing machines ( https://people.irisa.fr/Francois.Schwarzentruber https://people.irisa.fr/Francois.Schwarzentruber )/recursive_functions_to_turing_machines/ https://brilliant.org/wiki/turing-machines/ https://brilliant.org/wiki/turing-machines/
- sargstuff 5y ago
  non-deterministic turning machine: part 1: https://www.youtube.com/watch?v=gQnPM6sydkk https://www.youtube.com/watch?v=gQnPM6sydkk part 2: https://www.youtube.com/watch?v=9Bk11XgiC1E https://www.youtube.com/watch?v=9Bk11XgiC1E

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
  in cleaner/condensed version, part b: switch/case dispatch table with c support for assigning function(s) in switch to cpu threads.chiark.greenend.org.uk/~sgtatham/coroutines.html ) allows for programming language level IPC/pipes and in-language support for parallel programming! loads of fun for the compiler implimenter. perhaps, should be new language called rp-c
sargstuff 5y ago
quick rundown on theory behind grammar types/categories (aka expanded token parse ordering/magical intermediate data storage): https://devopedia.org/chomsky-hierarchy https://devopedia.org/chomsky-hierarchy https://www.geeksforgeeks.org/parse-tree-in-compiler-design/ https://www.geeksforgeeks.org/parse-tree-in-compiler-design/