onr:"swepub:oai:research.chalmers.se:5dae3b7c-169b-4f3d-8201-3e7c18472dc3"
Sökning: onr:"swepub:oai:research.chalmers.se:5dae3b7c-169b-4f3d-8201-3e7c18472dc3" > Efficient Divide-an...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Efficient Divide-and-Conquer Parsing of Practical Context-Free Languages
-
- Bernardy, Jean-Philippe, 1978 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Lindström Claessen, Koen, 1975 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
- (creator_code:org_t)
- 2013-09-25
- 2013
- Engelska.
- Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 48:9, s. 111-122
- Tidskriftsartikel (refereegranskat)
Abstract
Ämnesord
Stäng
- 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(n(3)) in the worst case, it improves to O(log (3) 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.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)
Nyckelord
- Complexity
- Iteration
- Parsing
- Divide-and-Conquer
- Context-Free Languages
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
- SIGPLAN Notices (ACM Special Interest Group on Programming Languages) (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Bernardy, Jean-P ...
- Lindström Claess ...
- Om ämnet
-
- TEKNIK OCH TEKNOLOGIER
- TEKNIK OCH TEKNO ...
- och Elektroteknik oc ...
- och Datorsystem
- Artiklar i publikationen
- SIGPLAN Notices ...
- Av lärosätet
- Chalmers tekniska högskola
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
