Tuesday, April 5, 2011

Reia: Now with a PEG parser

I haven't blogged about Reia in so long. Mea culpa! It's about this time that people start to think "I haven't heard about Reia in awhile. It must be dead." No, Reia is very much alive my friends, and making some pretty interesting progress... I hope to be able to announce some important new features around Reia's 3rd birthday. Stay tuned for that, but first a preview of things to come...


An experimental branch of Reia is now available which uses Neotoma to generate its parser thanks to some pretty impressive contributions by Graeme Defty. Neotoma is a Parsing Expression Grammar (PEG) based parser generator for Erlang, inspired by Packrat. Neotoma's author Sean Cribbs has also released Neotoma 1.5 with contributions by Graeme Defty which uses Erlang binaries internally and is substantially faster than the previous version.

Why does a PEG matter? PEGs make short work of problems that are extremely complex to handle when you attempt to subdivide the problem of parsing into separate scanning and parsing steps, such as how a traditional lex/yacc (or in Reia's case, leex/yecc) parser would operate. If you've ever attempted to look at the source code of the Ruby parser, you'll find some strange and confusing feedback between the lexer and the parser.

What's this for? Well the foremost reason is: interpolated strings. Ruby allows you to embed arbitrary Ruby code inside of any string using the #{...} syntax. This is a really great feature and one I managed to half-assed implement in Reia because I strongly believe in its awesomeness. However, Reia's implementation is a bit brittle and has a lot of implementations. Just recently I switched to the latest greatest version of leex which ships with the Erlang runtime and had to make some rather arcane changes to some code that uses leex internals, just to continue to support a partially functioning string interpolation mechanism.

Now, toss in some more fun complexities: the awesome /.../ regex literal syntax. We all love it, but why doesn't every language have it? What you may not realize is that this syntax is ambiguous in certain cases with the / and /= operators like it is in other languages like JavaScript. Now, for added fun, toss in the fact that regular expressions can interpolate just like strings, and you're beginning to see the makings of a gramatical nightmare.

All of these things are easy with a PEG. PEGs blend tokenization with parsing and allow comprehension of a much wider range of languages than is possible without pulling your hair out using lex/yacc-like tools, and much more than that, it's a very natural process with PEGs. PEGs are also by nature right-recursive, something that works quite well in immutable state languages like Erlang that have to build their syntax trees from right-to-left due to the nature of immutable singly linked lists. These lists only let you append elements on the left.

This sounds well and good, but unfortunately I have some bad news. Even after a few rounds of performance tuning, using an experimental branch of Neotoma that uses binaries internally instead of lists, the PEG parser is still about an order of magnitude slower than the leex/yecc version. Talking to Neotoma's author Sean Cribbs, it sounds like Neotoma might be doing an excessive amount of unnecessary copying internally. If PEGs pique your interest and you know a bit of Erlang you might take a peek at Neotoma and see if you can find some potential performance optimizations.

I would still like to merge the peg branch of Reia, and the PEG grammar fixes a lot of quirks in the present yecc grammar, but I'm still holding out until the performance is improved to closer to the leex/yecc speeds.

24 comments:

phil pirj said...

Congradulations on that. Huge respect to Graeme.
Reia is still my point of interest, and I have some experience with Neotoma as well. Hope to have some time to play with it this spring.

Aliya said...

Surveillancekart | CCTV System
Pestveda | Pest Control
Termite control
cctv installation services
best home security camera system

emma said...

cctv camera dealers in delhi
cp plus cctv camera online
hikvision camera online
cctv camera installation services in delhi
cctv camera installation services in gurugram
cctv camera installation services in gurgaon

shabnam praveen said...

Call girls in Kolkata
Call girls in Chandigarh
Call girls in Chandigarh
Call girls in Gurgaon
Call girls in Chandigarh
Call girls in Chandigarh

shabnam praveen said...

Call girls in Lucknow
Call girls in Guwahati
Call girls in Mumbai
Call girls in Jaipur
Call girls in Jaipur
Call girls in Jaipur
Call girls in Bangalore

call Girl said...

Call girls in Gurgaon
Call girls in Lucknow
Call girls in Guwahati

Call girl in Gurgaon
Call girl in Lucknow
Call girl in Guwahati
Bangalore call girls


Gurgaon call girls
Lucknow call girls
Guwahati call girls
Bangalore call girls


Gurgaon call girl
Lucknow call girl
Guwahati call girl
Bangalore call girl

Escorts in Gurgaon
Escorts in Lucknow
Escorts in Guwahati
Escorts in Bangalore


Escort services in Gurgaon
Escort services in Lucknow
Escort services in Guwahati
Escort services in Bangalore


Escort service in Gurgaon
Escort service in Lucknow
Escort service in Guwahati
Escort service in Bangalore


Gurgaon escorts
Lucknow escorts
Guwahati escorts
Bangalore escorts

Naincy Kumari said...

This is so much amazing .so,you can also visite my links.
call girls in kolkata
russian escorts in kolkata
kolkata call girls
call girls kolkata
escorts in kolkata
kolkata escort
housewife escorts in kolkata
college call girls in kolkata
call girls in park street
escorts in park street

call girls in gurgaon
call girl in gurgaon
gurgaon call girls
escorts in gurgaon
gurgaon escorts
gurgaon escort
Escort services in Gurgaon
Escort service in Gurgaon
russian escorts in gurgaon
housewife escorts in gurgaon
college call girls in gurgaon

Call girls in Noida
Call girl in Noida
Escorts in Noida
Escort services in Noida
Escort service in Noida
Noida Escorts
Noida Escort
Noida Call girls
Noida Call girl

call Girl said...

Gurgaon escorts
Lucknow escorts
Guwahati escorts
Bangalore escorts
call girls in bangalore

Gurgaon escort
Lucknow escort
Guwahati escort
Bangalore escort

Faridabad call girls
Faridabad call girl
Faridabad escorts
Faridabad escort
Escort services in Faridabad

Escort services in Faridabad
Call girls in Faridabad
Call girl in Faridabad
Faridabad escort services
Faridabad escort service

Escorts in Faridabad
Escorts in Faridabad
Escorts in Faridabad
Escorts in Faridabad

Escort in Faridabad
Escort in Faridabad
Escort in Faridabad
Escort in Faridabad

Escort services in Faridabad
Escort services in Faridabad
Escort services in Faridabad
Escort services in Faridabad

Escort service in Faridabad
Escort service in Faridabad
Escort service in Faridabad
Escort service in Faridabad

siska said...

Togel Sydney
Togel Singapore
Togel Hongkong
Prediksi Togel
Buku Mimpi
Angka Jitu Togel

Dida ELhaik said...

شركة كشف تسربات المياة ببريدة
شركة مكافحة حشرات ببريدة
شركة مكافحة النمل الابيض ببريدة
شركة رش مبيدات حشرية ببريدة
شركة تنظيف منازل ببريدة
شركة تنظيف مجالس ببريدة
شركة تنظيف كنب ببريدة
شركة تنظيف فلل ببريدة
شركة تنظيف شقق ببريدة
شركة تنظيف ببريدة

Dida ELhaik said...

شركة كشف تسربات المياة بعنيزة
شركة مكافحة حشرات بعنيزة
شركة مكافحة النمل الابيض بعنيزة
شركة رش مبيدات حشرية بعنيزة
شركة تنظيف منازل بعنيزة
شركة تنظيف مجالس بعنيزة
شركة تنظيف كنب بعنيزة
شركة تنظيف فلل بعنيزة
شركة تنظيف شقق بعنيزة
شركة تنظيف بعنيزة

bola88 said...

bandar judi
interqq
bandar togel
agen togel88
http://www.datahk8.com
idnpoker

Lisa said...

Hello my loved one! I want to say that this post is awesome, nice written and include almost all important information. I would like to peer more posts like this. I’ll right away grab your rss feed as I situs togel terpercaya can’t to find your email subscription hyperlink or e-newsletter service. Do you’ve any? Kindly allow me recognise so that I may subscribe.Thanks.

DEWA MESSUM said...

Nonton Film Bokep
DOMINOQQ
SASAQQ
BANDARPOKER

bahadur kaun said...

Buy your products online on Treasurebox store. Treasurebox provide you all the outdoor items household items which you will be easily buy on a single click in Newzealand. All the outdoor furniture nz products available at low prices with home delievery.

Unknown said...

pasarqq
wedeqq
agen togel
interqq
paito singapore
result togel
judi togel terpercaya
bandar sgp

dadyar said...

دستور تخلیه زمانی مطرح می شود که به واسطه قراردادی بین اشخاص در خصوص ملک، حق استفاده از ملک به طرف دیگر داده می شود (منظور همان قرارداد موجر و مستاجر است) اما پس از سر رسید تاریخ انقضاء قرارداد، مستاجر از تحویل ملک امتناء می کند.
در این مواقع موجر می تواند با ارائه دادخواست دستور تخلیه اقدام به بازپس گیری ملک تصرف شده فرماید. وکلا در این مواقع می توانند کمک شایانی به موجرین کنند تا هر چه سریعتر نه تنها حکم نخلیه صادر شود بلکه مراحل تخلیه نیز هر چه سریعتر طی شود. در صورت داشتن هرگونه سوال و یا نیاز به مشاوره می توانید از مشاوره رایگان انلاین و تلفنی گروه وکلای مستر دادیار استفاده نمایید.
دستور تخلیه فوری
همانطور که گفته شد در صورتی که تاریخ انتقضاء قرارداد فرا رسیده باشد. با ارائه دادخواست، دستور فوری تخلیه صادر می گردد. اما اگر به موجب شرط و یا مسائل دیگری صاحب ملک درخواست تخلیه ملک را داشته باشد، پس از بررسی های لازم و به حق بودن درخواست دستور صادر می گردد.
البته برای این امر شرایطی دیگری نیز لازم است از جمله:
قرارداد در دفتر اسناد رسمی تنظیم شده باشد و یا دو شاهد آن را امضا کرده باشند
مستاجر از پرداخت سه ماه اجاره خانه امنتاع کرده باشد.
ملک مورد اجاره را برای امر نا مشروع مورد استفاده قرار داده باشد و….
تفاوت خلع ید و دستور تخلیه
همان طور که در ابتدای بحث به آن پرداختیم، دادخواست تخلیه زمانی مطرح می گردد که قراردادی مابین طرفین وجود داشته باشد و اکنون به موجب سر رسید تاریخ انقضا و یا مواردی که به موجر حق باز پس گیری ملک را می دهد به وجود آید. اما در پرونده های خلع ید چنین نیست یعنی قرار دادی وجود ندارد تا بر مبنای آن دادخواستی تنظیم گردد. یعنی شخص مال غیر منقولی را به تصرف کرده است که در این صورت باید دادخواستی برای خلع ید تنظیم گردد.
شرایط طرح دستور تخلیه
در ابتدا به برخی از شرایط طرح دادخواست اشاره شد، که در این بخش به صورت کاملتری بیان خواهند شد.
مشخص بودن زمان اجاره
تنظیم اجاره نامه در دو نسخه
امضا شدن اجاره نامه توسط دو شاهد
مشخص بودن تاریخ انقضا قرارداد و به انقضا رسیدن قرارداد
در صورت فرا نرسیدن تاریخ انقضای، باید حداقل سه ماه مستاجر از پرداخت اجاره بها امتناء کرده باشد
استفاده نامشروع از ملک توسط مستاجر
نقض شرط عدم عدم انتقال به غیر توسط مستاجر
در صورت مطرح بودن سند رسمی در مورد اجاره، باید دادخواست برای گرفتن حکم تخلیه اقدام کرد و نه دستور تخلیه که به نسبت مدت زمان بیشتر طول خواهد کشید تا پرونده به نتیجه نهایی برسد.
مرجع صالح رسیدگی به دادخواست دستور تخلیه
در اماکن و املاکی که دارای سرقفلی هستند مرجع صالح رسیدگی دادگاه می باشد. اما در املاکی که فاقد سرقفلی هستند، نزدیکترین شورای حل اختلاف نزدیک ملک مرجع رسیدگی به این نوع شکایات می باشد.
به این موضوع با اهمیت توجه داشته باشید که هیچگاه مشورت با افراد با تجربه و کار بلد باعث پشیمانی نمی شود. پس حتما سعی کنید حتی در صورت نسپردن پرونده به وکیل، حتما به مشورت با آنها بپردازید. چرا که اشتباه در پرونده های حقوقی می تواند رای دادگاه را برگرداند و حق شما ضایع گردد.
هزینه دادرسی دستور تخلیه
دستورتخلیه از ناحیه صاحب خانه از جمله دعاوی غیر مالی محسوب می شود و هزینه دادرسی آن مساوی است با هزینه دادرسی دعاوی غیر مالی.
چگونگی اجرای دستور تخلیه
پس از صادر شدن دستور جهت تخلیه ملک به مستاجر ابلاغ می گردد. در صورتی که مستاجر از دستور پیروی نکن، ابلاغیه ای به کلانتری محل فرستاده می شود تا مامورین کلانتری نسبت به اجرای دستور و باز پس گیری ملک اقدام کنند.

Unknown said...

Agen http://pasarqq1.vip adalah situs terbaik ynag sama seperti dewaqq namun ada juga mejaqq yang berperan sama seperti hokiqq yang menyediakan http://interqq.site dan asik qq yang memiliki permainan yang sama. Agen http://wedeqq1.vip juga situs terbaik dan juga menyediakan tabel paito sd

Unknown said...

paito sydney
paito warna sydney
paito sgp
paito warna sgp
paito hk
paito harian hongkong
http://livedrawsgp.life

pemain togel said...

kingdomtoto
kingdomtoto
kingdomtoto
kingdomtoto
kingdomtoto
kingdomtoto

webspace said...

We are Webspace Inc. organization working as the Best Digital Marketing Company in USA and we give many services to our client that is website designing, website development, Search Engine Optimization, E-commerce web Designing, Software Development, Google Adword and Mobile Application.
Web Development company in Los Angeles
web design New York
web development New York
online marketing New York
ecommerce web development New York
internet marketing New York
SEO company New York
seo company USA
Web development company
Web development company California
Web development company Los angeles
Professional Web Design Services USA
Website Design Comapny
Web Design Company
webiste design services
Web Development Company in USA
Web Development Services in USA
website development company in usa
Ecommerce Website Development Company in USA
Ecommerce Website Development Services
custom ecommerce development
Ecommerce Website Development Company In Usa
CMS Web Design Services USACMS Website development company In Usa
Digital Marketing compnay in Usa
Online Marketing Services
Digital Marketing Company Usa
Seo Comapny In usa
Professional Software Development Company USA
software development company
custom software development company
custom software development In Usa
App Development Services USA
Mobile App development Company
Mobile Application Development Services

H J said...

KINGHORSETOTO
KINGHORSETOTO
KINGHORSETOTO

Puremelda said...

One unique characteristic of the firm's Custom Research Paper Services and College Paper Writing Services is that they offer the best market rates and actual research on all their Custom College Paper Writing Services.

Amber Collins said...

Hi was just seeing if you minded a comment. i like your website and the them you picked is super. I will be back.

www.caramembuatwebsiteku.com