Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #20876 > unrolled thread

I finally found a technique to parse left-recursive grammar in an simple elegant manner

Back to article view | Back to comp.lang.javascript

Contents

  I finally found a technique to parse left-recursive grammar in an simple elegant manner Simeon Chaos <simeon.chaos@gmail.com> - 2013-08-06 09:09 -0700
    Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner Simeon Chaos <simeon.chaos@gmail.com> - 2013-08-06 09:10 -0700
      Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2013-08-06 17:15 -0700
        Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner Simeon Chaos <simeon.chaos@gmail.com> - 2013-08-06 20:35 -0700
          Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-08-07 10:40 +0200
      Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-08-07 09:15 +0200
      Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner cau.giacomo190@gmail.com - 2014-01-18 12:36 -0800
        Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner cau.giacomo190@gmail.com - 2014-03-02 12:16 -0800
          Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner John Harris <niam@jghnorth.org.uk.invalid> - 2014-03-03 21:27 +0000
    Re: I finally found a technique to parse left-recursive grammar in an simple elegant manner "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2013-08-06 16:52 -0700

#20876 — I finally found a technique to parse left-recursive grammar in an simple elegant manner

All along, with the recursive descent parsing method, the left-recursive grammar is bad deal to hoe, as it will easily lead to infinite recursive call to function. For this reason, and now the mainstream parsers usually use the LR method,  with some tools such as lex / yacc, bison and the like, to generate parsers. Although some of languages adopt recursive descent parsing method, which had to limit their syntactic constructs, or make grammatical rule system unnecessarily complicated.

Last night, I finally found a simple and elegant way to process left recursive rules with the recursive descent method. After trying and failing for thirties or forties times in nearly five years, I get a beautiful result at last. I feel it's very cool. I experience the pleasure of success with persevere once again .

This method has the following features:
1. It can handle left recursion, including indirect left recursion.
2. It is simple and intuitive, the code of parser will be very readable.
3. It can achieve the same time complexity of O(n) as LL(k), LR method on proper grammar.
4 It is space-efficient. With this method, no transform table is needed, which is used in LR method. It do not need memo on every grammar symbol is need, which is usually adopted in peg/packrat parser. Instead, It only need memorize left recusive grammar symbol.
5. easy to learn, easy to use. the learning curve is flat. No new tools and libraries need be learned except the programming language with wich you code your parser.
6. Scanless parsing with this technique can be done, if you like.
7. flexible, adaptable. It can be arbitrarily accommodate different types of syntax by looking ahead or backtracking in the parser code.
8. Dynamic grammar becomes possible. Because the parser is directly coded in your compiler,  so you can dynamically modify the rules of grammar on the fly.
9.You can write the parser by hand with this technique easily.

Wikipedia about the peg grammar and stackoverflow 
http://stackoverflow.com/questions/1857022/limitations-of-peg-grammar-parser-generators 
http://en.wikipedia.org/wiki/Parsing_expression_grammar 
peg.js: javascript under the peg grammar parser generator: http://pegjs.majda.cz/ 
pyPEG,the peg grammar parser generator in javascript http://fdik.org/pyPEG/
jison: bison's java transport, which coffeescript uses  as its parser generator: http://zaach.github.io/jison/
bison http://en.wikipedia.org/wiki/Bison http://en.wikipedia.org/wiki/GNU_bison 
http://www.gnu.org/software/bison/manual/ 
the lex / yacc in python: http://www.dabeaz.com/ply/

Address left recursion in peg: http://link.springer.com/chapter/10.1007% 2F978-3-642-33182-4_4 # page-1
packrat parser for peg, The following paper discusses how to use memo mechanisms to implement left recursion
http://www.vpri.org/pdf/tr2007002_packrat.pdf 
Method is more complex, need to go through the parser generation phase, resulting in poor readability of parser code. Global memo mechanism is not flexible.

Two tools is mentioned here, which can handle left recursion:
http://stackoverflow.com/questions/4397039/any-peg-parser-capable-to-handle-left-recursion 
Ometa2: http://www.meta-alternative.net/mbase1.0.generic.zip

[toc] | [next] | [standalone]

#20877

I have written some experimental code, the experiment was successful. After a few days there will be a complete parser out.
I will use this new technology to write a parser by hand for my new dao language, I estimate that there should be some good result  within a week or two. Please pay attention to this github project: https://github.com/chaosim/daonode

Paste some experimental code I have written today, which verifies the feasibility of my ideas.
coffeescript Language: 

exports.parse = (element, text) -> 
  global.text = text 
  global.cursor = 0 
  global.tokens = [] 
  global.memo = {} 
  rules [element] (0) 

match = (c) -> 
  if text [cursor] is c 
    cursor + +; 
    true 

rules = { 
Binary: (start) -> 
  "Binary: 1 | Binary +1" 
  hash = 'Binary' + start 
  m = memo [hash] 
  if m is undefined 
    memo [hash] = rules.Unary (start) 
    rules.Binary (start) 
  else 
    if not match ('+') then delete memo [hash]; return m 
    a = rules.Unary (cursor) 
    if not a then delete memo [hash]; m 
    else memo [hash] = m + a; rules.Binary (start) 

Unary: (start) -> 
  c = text [cursor] 
  switch c 
    when '+' 
      cursor + +; 
      if text [cursor] == '+' then cursor + +; rules.Unary (cursor) +1; 
      else rules.Unary (cursor) 
    when '-' 
      cursor + +; 
      if text [cursor] == '-' then cursor + +; rules.Unary (cursor) -1 
      else-rules.Unary (cursor) 
    else 
      x = rules.Atom (start) 
      if text [cursor] == '+' and text [cursor +1] == '+' then cursor + = 2; x +1 
      else if text [cursor] == '-' and text [cursor +1] == '-' then cursor + = 2; x-1 
      else x 


Atom: (start) -> 
  switch text [cursor] 
    when '1 'then cursor + +; 1 
    when '(' then cursor + +; exp = rules.Binary (cursor); match (')'); exp 

} 

The following is a test adopted: 

 "Test parse left recursive": (test) -> 
    test.equal parse ('Binary', '1 '), 1 
    test.equal parse ('Binary', '+ +1'), 2 
    test.equal parse ('Binary', '1 + + '), 2 
    test.equal parse ('Binary', '1 - '), 0 
    test.equal parse ('Binary', '(1 -) -'), -1 
    test.equal parse ('Binary', '+1'), 1 
    test.equal parse ('Binary', '-1'), -1 
    test.equal parse ('Binary', '- 1'), 0 
    test.equal parse ('Binary', '1 +1 +1'), 3 
    test.equal parse ('Binary', '1 + (1 +1) '), 3 
    test.equal parse ('Binary', '(1 +1) + (1 +1)'), 4 
    test.equal parse ('Binary', '1 + (1 +1 +1) +1'), 5 
    test.done () 

This code representatively reflects the characterics in the recursive descent method. In the above code, a function corresponds to a grammar nonterminal. The program is simple and intuitive. By adopting a good expansion and derivision mechanism  according to memo, the infinite recursive call of the function is avoided.
I am very wonder that such a simple way had not been found for so many years? And I found  it after keeping trying many different ways, failed thirties or forties times, within almost five years. I tried some very complex method, including those method, based on python's yield statement (who can search yieldProlog if hope to know it), based on the continuation-based method(cps), but they all are not as good as this simple program, and once It seemed to have been solved, but the code is very complicated and ugly, in addition to problem with the time and space efficiency, I finally give up.
In addition, this new method with the python's yield statement, will be a very simple, intuitive, flexible and powerful handwritten parser program. You can refer to YieldProlog for more details.
Does anyone have a reasonable explanation?
Or maybe I made some mistakes in my ideas? I would appreciate you opinions very much.

[toc] | [prev] | [next] | [standalone]

#20881

On Tuesday, August 6, 2013 11:10:57 AM UTC-5, Simeon Chaos wrote:
> I have written some experimental code, the experiment was successful. After a few days there will be a complete parser out.

So the first post was just marketing?

> I will use this new technology to write a parser by hand for my new dao language, I estimate that there should be some good result  within a week or two. Please pay attention to this github project: https://github.com/chaosim/daonode
> 
> Paste some experimental code I have written today, which verifies the feasibility of my ideas.
> 
> coffeescript Language: 

This is a JavaScript newsgroup. Not a CoffeeScript newsgroup.

[snipping CS]

> This code representatively reflects the characterics in the recursive descent method. In the above code, a function corresponds to a grammar nonterminal. The program is simple and intuitive. By adopting a good expansion and derivision mechanism  according to memo, the infinite recursive call of the function is avoided.

You example is far too simplistic to be representative of much IMO. 

> I am very wonder that such a simple way had not been found for so many years?

I'd say simpler and more efficient methods were found decades ago and you were simply unaware of them

>And I found  it after keeping trying many different ways, failed thirties or forties times, within almost five years. I tried some very complex method, including those method, based on python's yield statement (who can search yieldProlog if hope to know it), based on the continuation-based method(cps), but they all are not as good as this simple program, and once It seemed to have been solved, but the code is very complicated and ugly, in addition to problem with the time and space efficiency, I finally give up.

I'd suggest reading some of the existing literature from last century, such as what was mentioned in my last response for starters

> In addition, this new method with the python's yield statement, will be a very simple, intuitive, flexible and powerful handwritten parser program. You can refer to YieldProlog for more details.

I suspect using yield for this task is far slower than you think.

> Does anyone have a reasonable explanation?
> 
> Or maybe I made some mistakes in my ideas? I would appreciate you opinions very much.

As I've expressed already, my opinion is that you need to research more into the existing techniques invented in the 1960s and onwards, and not only the current fads. I would also prefer to see a JavaScript example.

[toc] | [prev] | [next] | [standalone]

#20882

On Tuesday, August 6, 2013 11:09:33 AM UTC-5, Simeon Chaos wrote: 
>> All along, with the recursive descent parsing method, the left-recursive grammar is bad deal to hoe, as it will easily lead to infinite recursive call to function. 

> For any CFG, a parser can be written that runs in O(n^3). for both LL and LR it can be done in O(n). This has been known since the 1960s if not sooner. I don't know where you are getting your infinity from. There are justifiable reasons to allow left recursion in a grammar. 
Yes, it's the result of compiler theory and formal language theory since the 1960s if not sooner. That's what the GLR algoithm(Timato algorithm), Earley algorithm, CYK algorithm can do. "Recognition using the GLR algorithm has the same worst-case time complexity as the CYK algorithm and Earley algorithm: O(n3)." from [http://en.wikipedia.org/wiki/GLR_parser]
Maybe I have not express myself clearyly. I used the phrase "recursive descent" accurately. General recursive descent method by computing first set and follow set can be used as parser generator of LL grammar . I want to say it's hard to write parser in which every function is a grammar nonterminal symbol by hand  for grammars which have left recursion.

>>For this reason, and now the mainstream parsers usually use the LR method,  with some tools such as lex / yacc, bison and the like, to generate parsers. 

> Actually, it is because there are more languages in the class of LR grammars than LL. Plus many people find the grammars for LR languages more intuitive for constructs like arithmetic expressions (which are common in most languages). The tools are used as it is a very mind numbing process to build/maintain the corresponding DFAs, PDAs, FIRST and FOLLOW sets for the given grammar 

You are right.
But we need learn them before use these tools. When I wrote input for these tools, I feel I'm using a new mini language.

>> Although some of languages adopt recursive descent parsing method, which had to limit their syntactic constructs, or make grammatical rule system unnecessarily complicated. 

> If you wish to stay linear, there are trade-offs of course. It has been argued of course that semantics shouldn't be associated with phrase structures anyway, but instead associated with Lexemes directly (See Pratt's TDOP paper for an argument) 

In fact there are more languages which can be linear time complexity than those which can be processed by these tools, inluding LL(k), SLR, LALR, LR(0), LR(1).

>> Last night, I finally found a simple and elegant way to process left recursive rules with the recursive descent method. After trying and failing for thirties or forties times in nearly five years, I get a beautiful result at last. I feel it's very cool. I experience the pleasure of success with persevere once again . 

> If you read the Dragon Book or Michael Scott's book on Programming Language Pragmatics about 5 years ago, you could have saved yourself some effort methinks. 

I claimed my asserts with much efforts. I have passed the course of compiler theory in the university 20 years ago. I could not count I have read how many books and papers on compiler, parsing techniques, formal languages, natural language process. etc, since I chose natural language programming as the subject of my master paper and research interest. 
Anyway, I did not read Michael Scott's book on Programming Language Pragmatics. Thank you for your recommendation. I'll read it and hope to find something new for me. 

>> This method has the following features: 
>> 1. It can handle left recursion, including indirect left recursion. 
>> 2. It is simple and intuitive, the code of parser will be very readable. 
>> 3. It can achieve the same time complexity of O(n) as LL(k), LR method n proper grammar. 
>> 4 It is space-efficient. With this method, no transform table is needed, which is used in LR method. It do not need memo on every grammar symbol is need, which is usually adopted in peg/packrat parser. Instead, It only need memorize left recusive grammar symbol. 
>> 5. easy to learn, easy to use. the learning curve is flat. No new tools and libraries need be learned except the programming language with wich you code your parser. 
>> 6. Scanless parsing with this technique can be done, if you like. 
>> 7. flexible, adaptable. It can be arbitrarily accommodate different types of syntax by looking ahead or backtracking in the parser code. 
>> 8. Dynamic grammar becomes possible. Because the parser is directly coded in your compiler,  so you can dynamically modify the rules of grammar on the fly. 
>> 9.You can write the parser by hand with this technique easily. 

> [snipping ref dump] 
> I don't see a reference to anything concrete here... 
> So you rediscovered the OmetaJS and PEGs? 

I'm just saying about a new method to write parser by hand, as I demostrated in the code I posted later. The method is not much relevant to Ometa or PEG.

>> I have written some experimental code, the experiment was successful. After a few days there will be a complete parser out.
> So the first post was just marketing? 
I post the message both for sharing my result and for some marketing. I'm sorry for that if it disturded.

>> I will use this new technology to write a parser by hand for my new dao language, I estimate that there should be some good result  within a week or two. Please pay attention to this github project: https://github.com/chaosim/daonode 
>> Paste some experimental code I have written today, which verifies the feasibility of my ideas. 
>> coffeescript Language: 

> This is a JavaScript newsgroup. Not a CoffeeScript newsgroup. 

Coffeescript's just JavaScript

> [snipping CS] 

>> This code representatively reflects the characterics in the recursive descent method. In the above code, a function corresponds to a grammar nonterminal. The program is simple and intuitive. By adopting a good expansion and derivision mechanism  according to memo, the infinite recursive call of the function is avoided. 

> You example is far too simplistic to be representative of much IMO. 

I have tried writing the parser by hand in this style more then ten times for rules including left recusion. But I failed every times except last time :) 

>> I am very wonder that such a simple way had not been found for so many years? 

> I'd say simpler and more efficient methods were found decades ago and you were simply unaware of them 

Any parser hand-written like this, which processes direct and indirect left recusion?  I would appreciate it that you would be pleased to provide any concrete link to library, project or papers.

>> And I found  it after keeping trying many different ways, failed thirties or forties times, within almost five years. I tried some very complex method, including those method, based on python's yield statement (who can search yieldProlog if hope to know it), based on the continuation-based method(cps), but they all are not as good as this simple program, and once It seemed to have been solved, but the code is very complicated and ugly, in addition to problem with the time and space efficiency, I finally give up. 

> I'd suggest reading some of the existing literature from last century, such as what was mentioned in my last response for starters 

Thanks for your advice. I have read many of them, I will not stop reading them.

>> In addition, this new method with the python's yield statement, will be a very simple, intuitive, flexible and powerful handwritten parser program. You can refer to YieldProlog for more details. 

> I suspect using yield for this task is far slower than you think. 

Benchmark? The cost of yield statement? 

>> Does anyone have a reasonable explanation?  
>> Or maybe I made some mistakes in my ideas? I would appreciate you opinions very much. 

> As I've expressed already, my opinion is that you need to research more into the existing techniques invented in the 1960s and onwards, and not only the current fads. I would also prefer to see a JavaScript example. 

The golden rule of CoffeeScript is: "It's just JavaScript", again.

Below is the javascript code compiled from the above coffeescript code.

 exports.parse = function(element, text) {
    global.text = text;
    global.cursor = 0;
    global.tokens = [];
    global.memo = {};
    return rules[element](0);
  };

  match = function(c) {
    if (text[cursor] === c) {
      cursor++;
      return true;
    }
  };

  rules = {
    Binary: function(start) {
      "Binary: 1 | Binary+1";
      var a, hash, m;

      hash = 'Binary' + start;
      m = memo[hash];
      if (m === void 0) {
        memo[hash] = rules.Unary(start);
        return rules.Binary(start);
      } else {
        if (!match('+')) {
          delete memo[hash];
          return m;
        }
        a = rules.Unary(cursor);
        if (!a) {
          delete memo[hash];
          return m;
        } else {
          memo[hash] = m + a;
          return rules.Binary(start);
        }
      }
    },
    Unary: function(start) {
      var c;

      c = text[cursor];
      switch (c) {
        case '+':
          cursor++;
          if (text[cursor] === '+') {
            cursor++;
            return rules.Unary(cursor) + 1;
          } else {
            return rules.Unary(cursor);
          }
          break;
        case '-':
          cursor++;
          if (text[cursor] === '-') {
            cursor++;
            return rules.Unary(cursor) - 1;
          } else {
            return -rules.Unary(cursor);
          }
          break;
        default:
          x = rules.Atom(start);
          if (text[cursor] === '+' && text[cursor + 1] === '+') {
            cursor += 2;
            return x + 1;
          } else if (text[cursor] === '-' && text[cursor + 1] === '-') {
            cursor += 2;
            return x - 1;
          } else {
            return x;
          }
      }
    },
    Atom: function(start) {
      var exp;

      switch (text[cursor]) {
        case '1':
          cursor++;
          return 1;
        case '(':
          cursor++;
          exp = rules.Binary(cursor);
          match(')');
          return exp;
      }
    }
  };

------

In summary, I maybe have used the phrase "recursive decent" imprecisely. I mean I found a method to write parsers by hand, in which every function correspond a grammar nonterminal symbol, even if which is direct or indirect left recursive.  This method is different from the table-driven recursive decent method which generate the parser from LL(k) grammar, like the tools antlr, peg, packrat, etc.

[toc] | [prev] | [next] | [standalone]

#20885

[Supersede & Cancel; wrong attribution due to previous Google Groups bug]

Simeon Chaos wrote:

> [Michael Haufe (TNO) wrote: ]
>> This is a JavaScript newsgroup. Not a CoffeeScript newsgroup.
> 
> Coffeescript's just JavaScript

No, it is not.

<http://PointedEars.de/es-matrix>

-- 
PointedEars

Twitter: @PointedEars2
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#20883

Simeon Chaos wrote:

> Paste some experimental code I have written today, which verifies the
> feasibility of my ideas.
> coffeescript Language: 
> […]
> Or maybe I made some mistakes in my ideas? I would appreciate you opinions
> very much.

You should post to a newsgroup where the people subscribed to it are more 
familiar with the programming language you are using, or at least  
interested in the language you are attempting to parse with it.  In 
particular, how *exactly* does your posting relate to ECMAScript 
implementations?

That CoffeeScript transcompiles to an ECMAScript implementation, that 
Brendan Eich says it has influenced his thinking about the future of 
JavaScript™ and ECMAScript, and that both CoffeeScript and 
J(ava)Script/ECMAScript have “script” in it, does not mean that CoffeeScript 
is on-topic here.  CoffeeScript is not an ECMAScript implementation.

Further reading:
<http://net.tutsplus.com/articles/interviews/should-you-learn-coffeescript/>

ISTM from just scanning your posting that it presents that general an 
approach that it belongs in newsgroup dealing with computer science in 
general instead, for proper review.  Perhaps comp.compilers (moderated). 
However, Michael has pointed out that your proposal is lacking scientific 
research, so it may be better not to (re-)post it at all at this point.

Also, you should post to Usenet using your real (transliterated) name (Cao 
Xingming?), and not via Google Groups’ (currently) borken or any other 
(current, therefore likely buggy) Web interface.  For example, the more than 
80 printable characters per line that Google Groups is producing by default 
are – with few exceptions – not appropriate here.

<http://jibbering.com/faq/#posting>
<http://PointedEars.de/faq#posting>

-- 
PointedEars

Twitter: @PointedEars2
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#22703

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">

<html>
<head>
	<title>Untitled</title>
</head>

<body>

<script>

	//	https://groups.google.com/forum/#!search/left$20recursive/comp.lang.javascript/GN7b9Tr6j98/DoiHzi9i77oJ
	
    test('Binary', '1', 1)
    test('Binary', '++1', 2)
    test('Binary', '1++', 2)
    test('Binary', '1--', 0)
    test('Binary', '(1--)--', -1)
    test('Binary', '+1', 1)
    test('Binary', '-1', -1)
    test('Binary', '--1', 0)
    test('Binary', '1+1+1', 3)
    test('Binary', '1+(1+1)', 3)
    test('Binary', '(1+1)+(1+1)', 4)
    test('Binary', '1+(1+1+1)+1', 5)
	
	function test(rule, text, value) {
		document.write(rule, ' : \'', text, '\' == ', value, ' ', parse(rule, text) == value, '<br>')
	}

	function parse(rule, text) {
	
		var memo = {}
		var cursor = 0
		var rules = {Binary:Binary, Unary:Unary, Atom:Atom}
		return rules[rule](cursor)
		
		function match(c) {
			if (text.substr(cursor, c.length) !== c) return false
			cursor += c.length
			return true
		}
		
		function Binary(start) {
			// Binary: 1 | Binary+1
			var h = 'Binary' + start
			var m = memo[h]
			if (m === undefined) {
				memo[h] = Unary(start)
				return Binary(start)
			}
			if (!match('+')) {
				delete memo[h]
				return m
			}
			var u = Unary(cursor)
			if (!u) {
				delete memo[h]
				return m
			}
			memo[h] = m + u
			return Binary(start)
		}
		
		function Unary(start) {
			if (match('+')) {
				return match('+') ? Unary(cursor)+1 : +Unary(cursor)
			}
			if (match('-')) {
				return match('-') ? Unary(cursor)-1 : -Unary(cursor)
			}
			a = Atom(start)
			return match('++') ? a+1 : match('--') ? a-1 : a
		}
		
		function Atom(start) {
			if (match('1')) return 1
			if (match('(')) {
				var b = Binary(cursor)
				if (match(')')) return b
			}
		}
	}
</script>


</body>
</html>

[toc] | [prev] | [next] | [standalone]

#23366

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">

<html>
<head>
	<title>Untitled</title>
</head>

<body>

<script>
	
	//	https://groups.google.com/forum/#!search/left$20recursive/comp.lang.javascript/GN7b9Tr6j98/DoiHzi9i77oJ

	//test('Binary', '1+1+1', 3)

	//*
	test('Atom', '1', 1)
	test('Atom', '2', 2)
	test('Atom', '(1)', 1)
	// test('Binary', '()', 1) // stack overflow
	document.write('<br>')
	
	test('Unary', '1', 1)
	test('Unary', '+1', 1)
	test('Unary', '-1', -1)
	test('Unary', '++1', 2)
	test('Unary', '--1', 0)
	test('Unary', '1++', 2)
	test('Unary', '1--', 0)
	test('Unary', '(', 1) // invalid 
	test('Unary', '()', 1)
	test('Unary', '(1', 1)
	test('Unary', '1)', 1)
	test('Unary', '(1)', 1)
	document.write('<br>')
	
	test('Binary', '1', 1)
	test('Binary', '++1', 2)
	test('Binary', '1++', 2)
	test('Binary', '1--', 0)
	test('Binary', '(1--)--', -1)
	test('Binary', '+1', 1)
	test('Binary', '-1', -1)
	test('Binary', '--1', 0)
	test('Binary', '1+1+1', 3)
	test('Binary', '1+(1+1)', 3)
	test('Binary', '(1+1)+(1+1)', 4)
	test('Binary', '1+(1+1+1)+1', 5)
	test('Binary', '1-1-1', -1)
	test('Binary', '3+1', -1)
	document.write('<br>')
	//*/
	
		
	function test(rule, text, value) {
		try {
			document.write(rule, ' : \'', text, '\' == ', value, ' ', parse(rule, text) == value, '<br>')
		}
		catch (e) {
			document.write(rule, ' : \'', text, '\' == ', value, ' ', e, '<br>')
		}
	}

	function parse(rule, text) {
	
		var cursor = 0
		var rules = {Binary:Binary, Unary:Unary, Atom:Atom}
		var r = rules[rule](cursor)
		if (cursor == text.length - 1) throw 'invalid ' + rule +' at ' + cursor + ' [1]'
		return r
		
		function match(c) {
			if (text.substr(cursor, c.length) !== c) return false
			cursor += c.length
			return true
		}
		
		function Binary(start) {
			var v = Unary(start)
			if (v === undefined) return v
			for (;;) {
				if (match('+')) {
					var u = Unary(cursor)
					if (u === undefined) return v
					v += u
					continue
				}
				if (match('-')) {
					var u = Unary(cursor)
					if (u === undefined) return v
					v -= u
					continue
				}
				return v
			}
		}
		
		function Unary(start) {
			if (match('+')) {
				return match('+') ? Unary(cursor)+1 : +Unary(cursor)
			}
			if (match('-')) {
				return match('-') ? Unary(cursor)-1 : -Unary(cursor)
			}
			var a = Atom(start)
			if (a !== undefined) {
				return match('++') ? a+1 : match('--') ? a-1 : a
			}
			if (!match('(')) throw 'invalid Unary at ' + cursor + ' [2]'
			var b = Binary(cursor)
			if (b === undefined) return
			if (!match(')')) throw 'invalid Unary at ' + cursor + ' [3]'
			return match('++') ? b+1 : match('--') ? b-1 : b
		}
		
		function Atom(start) {
			if (match('1')) return 1
		}	
	}
</script>


</body>
</html>

[toc] | [prev] | [next] | [standalone]

#23369

On Sun, 2 Mar 2014 12:16:39 -0800 (PST), cau.giacomo190@gmail.com
wrote:

  <snip>
>	<title>Untitled</title>
  <snip>

Can this be true?

  John

[toc] | [prev] | [next] | [standalone]

#20880

On Tuesday, August 6, 2013 11:09:33 AM UTC-5, Simeon Chaos wrote:
> All along, with the recursive descent parsing method, the left-recursive grammar is bad deal to hoe, as it will easily lead to infinite recursive call to function. 

For any CFG, a parser can be written that runs in O(n^3). for both LL and LR it can be done in O(n). This has been known since the 1960s if not sooner. I don't know where you are getting your infinity from. There are justifiable reasons to allow left recursion in a grammar.

>For this reason, and now the mainstream parsers usually use the LR method,  with some tools such as lex / yacc, bison and the like, to generate parsers.

Actually, it is because there are more languages in the class of LR grammars than LL. Plus many people find the grammars for LR languages more intuitive for constructs like arithmetic expressions (which are common in most languages). The tools are used as it is a very mind numbing process to build/maintain the corresponding DFAs, PDAs, FIRST and FOLLOW sets for the given grammar

> Although some of languages adopt recursive descent parsing method, which had to limit their syntactic constructs, or make grammatical rule system unnecessarily complicated.

If you wish to stay linear, there are trade-offs of course. It has been argued of course that semantics shouldn't be associated with phrase structures anyway, but instead associated with Lexemes directly (See Pratt's TDOP paper for an argument)

> Last night, I finally found a simple and elegant way to process left recursive rules with the recursive descent method. After trying and failing for thirties or forties times in nearly five years, I get a beautiful result at last. I feel it's very cool. I experience the pleasure of success with persevere once again .

If you read the Dragon Book or Michael Scott's book on Programming Language Pragmatics about 5 years ago, you could have saved yourself some effort methinks.

> This method has the following features:
> 1. It can handle left recursion, including indirect left recursion.
> 2. It is simple and intuitive, the code of parser will be very readable.
> 3. It can achieve the same time complexity of O(n) as LL(k), LR method on proper grammar.
> 4 It is space-efficient. With this method, no transform table is needed, which is used in LR method. It do not need memo on every grammar symbol is need, which is usually adopted in peg/packrat parser. Instead, It only need memorize left recusive grammar symbol.
> 5. easy to learn, easy to use. the learning curve is flat. No new tools and libraries need be learned except the programming language with wich you code your parser.
> 6. Scanless parsing with this technique can be done, if you like.
> 7. flexible, adaptable. It can be arbitrarily accommodate different types of syntax by looking ahead or backtracking in the parser code.
> 8. Dynamic grammar becomes possible. Because the parser is directly coded in your compiler,  so you can dynamically modify the rules of grammar on the fly.
> 9.You can write the parser by hand with this technique easily.

[snipping ref dump]

I don't see a reference to anything concrete here...

So you rediscovered the OmetaJS and PEGs? 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web