CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Efficient divide-and-conquer parsing of practical context-free languages

Jean-Philippe Bernardy (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)) ; Koen Claessen (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers))
Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP p. 111-122. (2013)
[Konferensbidrag, refereegranskat]

We present a divide-and-conquer algorithm for parsing context-free languages efficiently. Our algorithm is an instance of Valiant's (1975), who reduced the problem of parsing to matrix multiplications. We show that, while the conquer step of Valiant's is O(n3) in the worst case, it improves to O(log3 n), under certain conditions satisfied by many useful inputs. These conditions occur for example in program texts written by humans. The improvement happens because the multiplications involve an overwhelming majority of empty matrices. This result is relevant to modern computing: divide-and-conquer algorithms can be parallelized relatively easily.

Nyckelord: Complexity, Context-free languages, Divide-and-conquer, Iteration, Parsing



Denna post skapades 2013-11-21. Senast ändrad 2014-01-20.
CPL Pubid: 187201

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)

Ämnesområden

Datorsystem

Chalmers infrastruktur