With this artifact, everyone can easily invent new languages
How is peasy (https://github/chaosim/peasy) simpler and more powerful than other parser tools? Simpler and more powerful? Maybe it is a bit contrary to common sense. True or false? To affirm, please give this project (https://github.com/chaosim/peasy) a glimpse at first. Because of being simple , you can comprehend it in a little while; because of being powerful, it will deserve your every minute. All along, the design of programming languages is a complex task. Because we need to understand the esoteric compiler theory and technology, and one of the most critical and very difficult part is to define the rules of the new language and to parse with them.To solve this problem, there have been many theories , techniques and tools . These tools can be roughly divided into two categories: one is parser generator, another is to write the parser by hand with or without a parser library. The parser generator generally based on some type of formal languages , by which the generator make the lexer and parser from some rules. Strong aspect of these tools is that they can produce the most efficient parser support for their own form of language types , according to the characteristics of formal language , generally ensures linear time complexity. Commonly divided into three types : LR technology , LL technology , PEG technology. LR technology language has shift/reduction , from the bottom up , the most right derived and other technical features , they can only support LR languages , more accurately, mainly LALR variants , plus some special treatment for the priority of operator. One of the most famous was undoubtedly the lex / yacc and its numerous subsequent variants ( such as bison, jison (javascript language ), ply (python lex / yacc) , etc. ) . LL technology has a top-down form of the language , recursive descent , the most left-dereived and other technical features , although the concept is easier to understand than the LR language , but because LL covers less languages, so not used as universal as lex / yacc. Representative products are antlr. PEG technology refers to parsing expression grammar parser generator. peg is a kind of formal grammar particularly suited to be parsed, currently there are already many tools appear. The most common method is packrat algorithm based implementations. Such as rats, ometa (there are many versions , such as ometa / squeak, ometa-js, pyMeta etc. ), pyPEG under python, peg.js under javascript, treetop and citrus under ruby, and so on. No matter what type of parser generator , the method to use them is to design rules for these tools , and then the tools generate parser. This is the difficult aspects. First, the object program is generated based on the state transfer and stack process, it is difficult to understand, debug and modify. Second, we must understand parser theory and technology of these tools is based on, the rules used by these tools is actually a domain-specific language , their expressivenes is very limited, while we must understand and become familiar with the new language in order to design rules. Third, we must embed certain processing ( abstract syntax tree structure , semantics, error reporting and handling , etc) in the form of object parser language into lex/parser rules. Difficulties in these areas prevent the most programmers to easily use this type of tool. Meanwhile, people have also been pursuing a more relaxed and flexible approach to write parsers. Most of these methods produce tools can be classified as combinational parser library , or peg grammar-based peg library . Use of such libraries, programmers can use their own language in daily use to design a new universal language , parsing text, so they are used more freguently. Representative works is parsec under haskell language which maybe is the most mature and powerful. However, because haskell is too academic, and parsec is not universally popular. c + + language has boost phoenix library, probably because it depends on the c++ template, an advanced language features, it has not been widely used too. Python has pyparsing, which is used by many users. For specific questions , there are many applications do not use any tools or libraries, but manually write the entire parser , for example: cpython implementation, esprima for javascript. However, unfortunately, in their grammar and parsing of these tools, there are two obvious difficulties not been solved: the first is left recursive grammar, because left-recursive function will lead to an unconditional infinite recursion. The second is the parsing efficiency. In order to obtain a linear time complexity , we should only parse same syntax component only once at any position. To achieve the latter, the result of parsing is required. Meanwhile , the parser also need to be considered in conjunction to produce abstract syntax trees , semantic processing , error handling , etc.
Re: With this artifact, everyone can easily invent new languages
Yes， it's complex to design a new language. So don't let the tool stand in the way. There is a saying: Grinding a chopper will not hold up the work of cutting firewood. 在 2014年1月11日星期六UTC+8上午10时17分33秒，Chris Angelico写道： > On Sat, Jan 11, 2014 at 11:59 AM, Simeon Chaos wrote: > > > All along, the design of programming languages is a complex task. Because > > we need to understand the esoteric compiler theory and technology, and one > > of the most critical and very difficult part is to define the rules of the > > new language and to parse with them.To solve this problem, there have been > > many theories , techniques and tools . These tools can be roughly divided > > into two categories: one is parser generator, another is to write the > > parser by hand with or without a parser library. > > > > > > > No tool will change the fact that the *design* of a language is a > > complex task. Long before you get to implementing anything, you have > > to decide what your language will look like, what its special features > > are, how it distinguishes one thing from another, etc etc etc. That > > work won't change based on the tool you use - or rather, if it DOES > > change, it's because the tool is too restrictive. First write some > > code in your new language, then and only then work out how to > > implement an interpreter/compiler. The first part of the job is pretty > > complex (and extremely important), and tools don't come into play till > > the second. > > > > ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: With this artifact, everyone can easily invent new languages
Thank you, James. I didn't know this group before. I'll post this message there. 在 2014年1月11日星期六UTC+8下午3时47分33秒，James Harris写道： > "Simeon Chaos" wrote in message > > news:bb7d8d30-845a-4a3d-9b03-dee71ef42986 @googlegroups.com... > > > ? 2014?1?11UTC+8??10?17?33?,Chris Angelico??: > > > > On Sat, Jan 11, 2014 at 11:59 AM, Simeon Chaos wrote: > > > > > > > > > All along, the design of programming languages is a complex task. > > > > > Because we need to understand the esoteric compiler theory and > > > > > technology, and one of the most critical and very difficult part is to > > > > > define the rules of the new language and to parse with them.To solve > > > > > this problem, there have been many theories , techniques and tools . > > > > > These tools can be roughly divided into two categories: one is parser > > > > > generator, another is to write the parser by hand with or without a > > > > > parser library. > > > > > Yes, it's complex to design a new language. So don't let the tool stand in > > > the way. There is a saying: Grinding a chopper will not hold up the work > > > of cutting firewood. > > > > To the OP: this is a suitable topic for comp.lang.misc which is used for > > discussions about programming language design and implementation such as > > parse mechanisms. > > > > James -- https://mail.python.org/mailman/listinfo/python-list
Peasy: an easy but powerful parser
I've released Peasy, which is an easy but powerful parser. Peasy brings a new method to write the parser. with Peasy, you write the parser by hand, just like to write any other kind of program. Do not be confused by "by hand", with the method brought by Peasy, it's easier and more powerful than using other tools or libraries. Peasy presents itself as a module of single file. To use Peasy, copy peasy.py to your project, read it, modify it, write the grammar rules, and remove any unnecessary stuffs in Peasy, and parse with the grammar. Peasy has an simple, elegant and fast support for direct/indirect left recursive grammar, See [here]( http://chaosim.github.io/peasy/doc/peasy.html#peasysample ) for a concrete sample. The [annotated code]( http://chaosim.github.io/peasy/doc/pypeasy.html ) is best document for Peasy at the moment. -- http://mail.python.org/mailman/listinfo/python-list
What would happen when lisp meets prolog in python? Dao and Dinpy arises!
Dao is the new generation programming system implemented by a
functional logic solver,
unifying code with data, grammar with program, logic with functional,
compiling with running.
Would you please to have a look at my dao and dinpy?
http://pypi.python.org/pypi/daot
https://github.com/chaosim/dao
The feature of dao and dinpy:
* Mix functional and logic programming like prolog and lisp in python.
* A most powerful parser is provided, which have the power all of the
other parsers do not have. below is the list of some parser and
algorithms: parsec(haskell), packrat, earley parser, glr parser,
antlr, lex/yacc.
What's the magic behind the dao? See samples\sexpression.py and
testsexpression.py for a sample.
this is the key tips to the dao's dynamic grammar, which will become
a most powerful tool:
(sexpression, function(
# dynamic grammar arises!
([Result], and_p(char('{'), sexpression(Expr2), char('}'),
setvalue(Result,
eval_(pycall(sexpression2daoexpression, Expr2),
([Expr], atom_expression(Expr)),
([Expr], bracketExpression(Expr)),
([Expr], puncExpression(Expr))),
# the kernel of dynamic grammar
(eval_parse_result, function(
([Result], and_p(sexpression(Expr2), eoi,
is_(Result, eval_(pycall(sexpression2daoexpression,
Expr2))),
--
http://mail.python.org/mailman/listinfo/python-list
overview on dao
Dao is a a functional logic solver (similar to lambdaProlog, Curry) written in python. The links related to dao are here: pypi distribution and document: http://pypi.python.org/pypi/daot code repository: https://github.com/chaosim/dao dao groups on google: Group name: daot, Group home page: http://groups.google.com/group/daot, Group email address: d...@googlegroups.com old stuffs: http://code.google.com/p/daot(old, deprecated) google+ pages: https://plus.google.com/112050694070234685790 Dao has the features such as * lisp style programming: * call/cc, block/return-from, unwind-protect, catch/throw; Dao is implemented by continuation passing style, so it is natural to implement such stuff. And I have some little improvement to the trampoline technology because I need it coexist with the technology of using yield statement to implement unifying and backtracking. The code for evaluating lisp style expression is borrowed from the book "Lisp in Small Pieces" wrote by Christian Queinnec and Ecole Polytechnique. * function and macro; The concept of function and macro in dao become more general than in lisp, because we can define them with multiple rules and take advantage of unifying and backtracking. * eval, so called meta circular evaluation. * prolog style programming: * logic variable and unify; * backtracking; * findall, repeat/fail, call, once, and so on; * cut. At first, unify is implemented by using exception, and backtracking by using two continuations(succeed continuation and fail continuation) technology, borrowed the code from pypy prolog. Now, the fail continuation is removed, and both unifying and backtracking is implemented by using 'yield' statement, which I learned from YieldProlog (http://yieldprolog.sourceforge.net). Dao run faster than before by using yield statement, removing class definition of continuation, and not boxing atomic and list values(compare to pypy prolog without translation or jit). Up to now I do not use the pypy's translation or jit feature to speedup, and all of the tests in dao 0.7.3 run in about two minutes. * many other useful builtins that simulate lisp and prolog primitives. * some builtins that cooperate with python. * builtin parser, which is the most powerful parser I have seen. The parser in dao is basically a recursive decent parser with backtracking, but It also support direct or indirect left recursive rules by using memorization when needed. The programmer can toggle memorization of any command that is not left recursive. the grammar in dao is some similar to DCG(definite clause grammar), but is more flexible than DCG. It have the expressive power beyond context free or sensitive grammar, parsing expression grammar. Dao can be used to parse any object, not limiting to text. Many builtin terminal and combinative parsing primitives are provided. In dao, I have found and implemented the unrivalled technology to uniting parser and evaluator by the meta circular evaluation. So Dao can be used to implement a programming language in which the syntax is dynamic, that is to say, the syntax can be defined on the fly by the programmer easily. A little sample to demonstrate this technology is given in the files dao/samples/sexpression.py and dao/dao/tests/ testsexpresson.py. - Dinpy: a child language born and live in python. Dinpy can be looked as the syntax sugar for dao in python. It arises accidentally when I wrote tests for dao. A detailed introduction is as follows: I hate the too many parentheses when I wrote tests for the 'let' statement of lisp, so I replace embedded tuples with dict for the bindings, and after the spark of inspiration, the door to dinpy was open. I learned a new method for inventing a new language from it: use the syntax based on the operator of the mother language for building the child language. -- I have written some Chinese documents for dao, but few English. The Chinese document is not complete yet. With the functional logic programming and dynamic grammar on the shoulders of the great python, many possibilities arises with dao, such as parsing, inventing embedded DSL with operator syntax, independent domain specific language or general language, text processing, natural language processing, expert system, artificial intelligence, web application, and so on. Now: * I hope more people know and use dao. Or maybe something wrong in dao prevent it being used in real application, and I hope to know what it is. * Maybe anyone have interest and time to join in developing dao or writing some documents or articles? * More tests are needed always, and I hope to get some bug report from any other people. * the benchmarks of the dao, comparation with similar package, and so on. * I have a long todo list, I hope someone
simpler over view on dao: a functional logic solver with builtin parsing power, and dinpy, the sugar syntax for dao in python
Dao is a a functional logic solver (similar to lambdaProlog, Curry)
written in python. The links related to dao are here:
pypi distribution and document: http://pypi.python.org/pypi/daot
code repository: https://github.com/chaosim/dao
dao groups on google: http://groups.google.com/group/daot,
d...@googlegroups.com
old stuffs: http://code.google.com/p/daot(old, deprecated)
google+ pages: https://plus.google.com/112050694070234685790
Dao has the features such as
* lisp style programming:
* call/cc, block/return-from, unwind-protect, catch/throw;
* function and macro;
* eval, so called meta circular evaluation.
* prolog style programming:
* logic variable and unify;
* backtracking;
* findall, repeat/fail, call, once, and so on;
* cut.
* many other useful builtins that simulate lisp and prolog
primitives.
* some builtins that cooperate with python.
* builtin parser, which is the most powerful parser I have seen, it
support the features as below:
* paramater grammar, similar to DCG( definite clause grammar),
but more flexible
* dynamic grammar,
* left recursive
* memoriaziont parsing result
* many builtins, include terminal and cominative matchers.
-
Dinpy: a child language born and live in python.
Dinpy can be looked as the syntax sugar for dao in python. A piece
of code in dinpy is listed as below:
parse_text(char(x1)+any(~char('b')+some(char(x1)))+eoi,
'ab'),
let( i<<0 ). do[ repeat, prin(i), ++i, iff(i<3).do[fail] ],
letr( a << fun(x) [ and_p(b(x),c(x)) ]
[ d(x) ],
b << fun(1) ['b1']
(4) ['b4'],
c << fun(4) ['c4'],
d << fun(3) ['d3'],
).do[
a(x), prin(x) ],
each(i)[1:3].
loop[prin(i)],
i << 0,
loop[ i << i+1, prin(i)].when(i==3),
case(1).
of(1)[prin(1)].
of(2)[prin(2)]
--
Some Chinese documents for dao is written, but few English. The
Chinese document is not complete yet.
With the functional logic programming and dynamic grammar on the
shoulders of the great python, many possibilities arises with dao,
such as parsing, inventing embedded DSL with operator syntax,
independent domain specific language or general language, text
processing, natural language processing, expert system, artificial
intelligence, web application, and so on.
Now:
* I hope more people know and use dao. Or maybe something wrong in dao
prevent it being used in real application, and I hope to know what it
is.
* Maybe anyone have interest and time to join in developing dao or
writing some documents or articles?
* More tests are needed always, and I hope to get some bug report from
any other people.
* the benchmarks of the dao, comparation with similar package, and so
on.
* I have a long todo list, I hope someone else can join in dao project.
--
http://mail.python.org/mailman/listinfo/python-list
Re: overview on dao
On Nov 9, 1:52 am, Dennis Lee Bieber wrote: > On Mon, 7 Nov 2011 21:10:59 -0800 (PST), Simeon Chaos > declaimed the following in > gmane.comp.python.general: > > > Dao is a a functional logic solver (similar to lambdaProlog, Curry) > > written in python. The links related to dao are here: > > Unfortunately the name is in conflict with M$ DAO (Data Access > Objects), the precursor to ADO. Every time I see "Dao" my mind goes "JET > database". > -- > Wulfraed Dennis Lee Bieber AF6VN > wlfr...@ix.netcom.com HTTP://wlfraed.home.netcom.com/ Yeah, here "dao" is from The book of Dao" by Laozi, means the way of the world go. -- http://mail.python.org/mailman/listinfo/python-list
Re: overview on dao
On Nov 9, 8:55 am, MRAB wrote: > On 09/11/2011 00:13, Simeon Chaos wrote: > > > > > > > > > > > On Nov 9, 1:52 am, Dennis Lee Bieber wrote: > >> On Mon, 7 Nov 2011 21:10:59 -0800 (PST), Simeon Chaos > >> declaimed the following in > >> gmane.comp.python.general: > > >>> Dao is a a functional logic solver (similar to lambdaProlog, Curry) > >>> written in python. The links related to dao are here: > > >> Unfortunately the name is in conflict with M$ DAO (Data Access > >> Objects), the precursor to ADO. Every time I see "Dao" my mind goes "JET > >> database". > >> -- > >> Wulfraed Dennis Lee Bieber AF6VN > >> wlfr...@ix.netcom.com HTTP://wlfraed.home.netcom.com/ > > > Yeah, here "dao" is from The book of Dao" by Laozi, means the way of > > the world go. > > Perhaps you should call it "LaoZiDao". I just prefer shorter name. -- http://mail.python.org/mailman/listinfo/python-list
dao 0.7.4 released
What's new in dao 0.7.4? *Release date: 2011-11-10 * new in code: * quasiquote, unquote, unquote_slicing is implemented. * directly evaluate sexpression in solver * some builtins for define, set and get global, outer and local var * lisp style macro: expand and eval on UserMacro -- http://mail.python.org/mailman/listinfo/python-list
