5 ms·

So, given the much discussed limitations of reg-exps and the desire to parse context-free grammars. My question is, why are we still using regular expressions.

by rocqua 7y ago

So, given the much discussed limitations of reg-exps and the desire to parse context-free grammars. My question is, why are we still using regular expressions. Or rather, why isn't there something as easy to use as regular expressions that can processes context-free grammars?

andrewflnr 7y ago
I don't know if it's possible to do the "string describing a set strings" thing that regex does with more powerful parsing while maintaining the ease of use. CFGs make heavy use of named sub-languages (productions). A regex-style parser would at least have to have some kind of recursion-inducing metacharacter.
- YeGoblynQueenne 7y ago
  How about this for ease-of-use? sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. Reads -and behaves- as BNF. Strings in []'s are terminals, the rest are nonterminals. It's directly executable as a logic program (it's Prolog syntactic sugar).
  - carapace 7y ago
    And this can be used to generate sentences as well as parse them. ;-)
    - YeGoblynQueenne 7y ago
      Indeed. I tend to forget how counter-intuitive this is. With DCGs you get your recognisers for nothing and your generators for free. As I like to say.
  - andrewflnr 7y ago
    That looks great, but it's hard to position it as a regex competitor. I should be more explicit about what I mean by "regex-style": The cool thing about regex that makes them so approachable is that they kind of look like the thing they're describing/matching. Your thing here mostly does not.
    - YeGoblynQueenne 7y ago
      "My thing here" is a grammar so it describes a class of strings. Perhaps this is why it looks to you unlike what it describes? You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history: \[13\/13,15\/12,24-24] You could write this like so in DCG notation: s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']']. And that would match the string "[13/13,15/12,24-24]", no less, no more. DCGs are Turing-complete, so you can go all the way from programs to finite automata when you write a pattern to match. They're not really a regex competitor. They were invented in the '70s as a formalism for context-free grammars to be used in representing natural language. They fit right into the logic programming language Prolog that was created soon after (and by some of the same people).
      - andrewflnr 7y ago
        Well, we started this subthread looking for alternatives to regex, so if DCGs aren't in the running I'm not sure what your point is. Also, I happen to believe Turing-completeness is a misfeature for this job.
        YeGoblynQueenne 7y ago
        The OP asked for "something as easy to use as regular expressions that can processes context-free grammars". You requested ease-of-use. I proposed DCGs. They are not an alternative to regexes in the sense that regexes can't represent anything beyond regular grammars, including CFGs. They can be as simple or as complicated as you want them and they are easy to use. I'm not sure what is a "misfeature". What do you mean? Edit: Apologies if I sound too terse. I'm confused by the terminology of "competitor", "alternative" etc. Are we in some kind of competition to find a technological solution that will take some prize? If so, I'd like to know the rules before I commit to any solution. What exactly are we trying to achieve here?
YeGoblynQueenne 7y ago
There are Definite Clause Grammars (which can also represent context-sensitive languages) but they are a Prolog thing: https://en.wikipedia.org/wiki/Definite_clause_grammar#Example https://en.wikipedia.org/wiki/Definite_clause_grammar#Exampl...
zokier 7y ago
Something like Perl6 grammars[1], or maybe Rosie Pattern Language[2]? Of course Perl6 regexes also go well beyond regular expressions, and I suspect they could be used to match context-free grammars if pressed hard enough. Both P6 grammars and RPL are based on parsing expression grammars, and there are also tools/libraries for many other languages based on PEGs. But now you are entering in the scary realm of parsers and parser generators and all that jazz, and can debate how easy to use they really are. [1] https://docs.perl6.org/language/grammars https://docs.perl6.org/language/grammars [2] https://developer.ibm.com/open/projects/rosie-pattern-language/ https://developer.ibm.com/open/projects/rosie-pattern-langua...
- wahern 7y ago
  PEGs are amazing precisely because they're as easy to use as, if not easier than, common regular expression syntax. PEGs are literally the same as regular expressions except 1) alternations are ordered, 2) zero-width assertions are formalized, and 3) quantifiers match greedily. This is effectively the same behavior as the Perl-compatible regular expressions with which most people are familiar. Many PEG engines, especially for dynamic languages, permit grammar composition using first-class variables. That might be a small barrier to people more familiar with the terseness and conceptual simplicity of regular expressions as string'ish values. But it's fairly trivial to implement the latter using PEGs. For example, LPeg provides a small auxiliary module for doing that: http://www.inf.puc-rio.br/~roberto/lpeg/re.html http://www.inf.puc-rio.br/~roberto/lpeg/re.html Also, Rosie seems amazing. I've not yet had the opportunity to make use of it, but I attended a presentation of Rosie by the author at a Lua workshop which left me very impressed.
heinrichhartman 7y ago
I have been a happy user of PEG grammars for a while: https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Parsing_expression_grammar In particular this lua implementation: http://www.inf.puc-rio.br/~roberto/lpeg/re.html http://www.inf.puc-rio.br/~roberto/lpeg/re.html It let's you write stuff like this: list <- (name s)* name <- [a-z][a-z]* s <- %s* Features: - Looks like EBNF - Regular expressions are a subset - Fast parser.

by rocqua 7y ago

andrewflnr 7y ago

I don't know if it's possible to do the "string describing a set strings" thing that regex does with more powerful parsing while maintaining the ease of use. CFGs make heavy use of named sub-languages (productions). A regex-style parser would at least have to have some kind of recursion-inducing metacharacter.

YeGoblynQueenne 7y ago
How about this for ease-of-use? sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. Reads -and behaves- as BNF. Strings in []'s are terminals, the rest are nonterminals. It's directly executable as a logic program (it's Prolog syntactic sugar).
- carapace 7y ago
  And this can be used to generate sentences as well as parse them. ;-)
  - YeGoblynQueenne 7y ago
    Indeed. I tend to forget how counter-intuitive this is. With DCGs you get your recognisers for nothing and your generators for free. As I like to say.
- andrewflnr 7y ago
  That looks great, but it's hard to position it as a regex competitor. I should be more explicit about what I mean by "regex-style": The cool thing about regex that makes them so approachable is that they kind of look like the thing they're describing/matching. Your thing here mostly does not.
  - YeGoblynQueenne 7y ago
    "My thing here" is a grammar so it describes a class of strings. Perhaps this is why it looks to you unlike what it describes? You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history: \[13\/13,15\/12,24-24] You could write this like so in DCG notation: s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']']. And that would match the string "[13/13,15/12,24-24]", no less, no more. DCGs are Turing-complete, so you can go all the way from programs to finite automata when you write a pattern to match. They're not really a regex competitor. They were invented in the '70s as a formalism for context-free grammars to be used in representing natural language. They fit right into the logic programming language Prolog that was created soon after (and by some of the same people).
    - andrewflnr 7y ago
      Well, we started this subthread looking for alternatives to regex, so if DCGs aren't in the running I'm not sure what your point is. Also, I happen to believe Turing-completeness is a misfeature for this job.
      - YeGoblynQueenne 7y ago
        The OP asked for "something as easy to use as regular expressions that can processes context-free grammars". You requested ease-of-use. I proposed DCGs. They are not an alternative to regexes in the sense that regexes can't represent anything beyond regular grammars, including CFGs. They can be as simple or as complicated as you want them and they are easy to use. I'm not sure what is a "misfeature". What do you mean? Edit: Apologies if I sound too terse. I'm confused by the terminology of "competitor", "alternative" etc. Are we in some kind of competition to find a technological solution that will take some prize? If so, I'd like to know the rules before I commit to any solution. What exactly are we trying to achieve here?

YeGoblynQueenne 7y ago

There are Definite Clause Grammars (which can also represent context-sensitive languages) but they are a Prolog thing: https://en.wikipedia.org/wiki/Definite_clause_grammar#Example https://en.wikipedia.org/wiki/Definite_clause_grammar#Exampl...

zokier 7y ago

Something like Perl6 grammars[1], or maybe Rosie Pattern Language[2]? Of course Perl6 regexes also go well beyond regular expressions, and I suspect they could be used to match context-free grammars if pressed hard enough. Both P6 grammars and RPL are based on parsing expression grammars, and there are also tools/libraries for many other languages based on PEGs. But now you are entering in the scary realm of parsers and parser generators and all that jazz, and can debate how easy to use they really are. [1] https://docs.perl6.org/language/grammars https://docs.perl6.org/language/grammars [2] https://developer.ibm.com/open/projects/rosie-pattern-language/ https://developer.ibm.com/open/projects/rosie-pattern-langua...

wahern 7y ago
PEGs are amazing precisely because they're as easy to use as, if not easier than, common regular expression syntax. PEGs are literally the same as regular expressions except 1) alternations are ordered, 2) zero-width assertions are formalized, and 3) quantifiers match greedily. This is effectively the same behavior as the Perl-compatible regular expressions with which most people are familiar. Many PEG engines, especially for dynamic languages, permit grammar composition using first-class variables. That might be a small barrier to people more familiar with the terseness and conceptual simplicity of regular expressions as string'ish values. But it's fairly trivial to implement the latter using PEGs. For example, LPeg provides a small auxiliary module for doing that: http://www.inf.puc-rio.br/~roberto/lpeg/re.html http://www.inf.puc-rio.br/~roberto/lpeg/re.html Also, Rosie seems amazing. I've not yet had the opportunity to make use of it, but I attended a presentation of Rosie by the author at a Lua workshop which left me very impressed.

heinrichhartman 7y ago

I have been a happy user of PEG grammars for a while: https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Parsing_expression_grammar In particular this lua implementation: http://www.inf.puc-rio.br/~roberto/lpeg/re.html http://www.inf.puc-rio.br/~roberto/lpeg/re.html It let's you write stuff like this: list <- (name s)* name <- [a-z][a-z]* s <- %s* Features: - Looks like EBNF - Regular expressions are a subset - Fast parser.