Back to Search
Start Over
Parsing Partially Ordered Multisets
- Source :
- International Journal of Foundations of Computer Science, 8(4), 379-407. World Scientific
- Publication Year :
- 1997
- Publisher :
- World Scientific Pub Co Pte Lt, 1997.
-
Abstract
- A partially ordered multiset or pomset is a generalization of a string in which the total order has been relaxed to a partial order. Strings are often used as a model for sequential computation; pomsets are a natural model for parallel and distributed computation. By viewing pomsets as a generalization of strings, the question is raised whether concepts from language theory can be generalized to pomsets. An important area in the theory of languages is parsing theory. This paper develops the fundamentals of a parsing theory for pomsets, called PLR parsing. It is based on the LR-parsing technique, which is the most powerful deterministic parsing technique in language theory. The basic algorithm in the class of PLR parsing algorithms, the PLR(0) algorithm is explained in detail.
- Subjects :
- Multiset
Theoretical computer science
Parsing
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
computer.software_genre
Top-down parsing
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Parser combinator
Computer Science (miscellaneous)
Top-down parsing language
S-attributed grammar
Deterministic parsing
Algorithm
computer
Mathematics
Bottom-up parsing
Subjects
Details
- ISSN :
- 17936373 and 01290541
- Database :
- OpenAIRE
- Journal :
- International Journal of Foundations of Computer Science
- Accession number :
- edsair.doi.dedup.....7ff6aae9179c1acf49f83fb80f72c1bb