View source for Deterministic Pushdown Automaton

A '''deterministic pushdown automaton''' (DPDA) is a restricted form of [[Pushdown Automaton|pushdown automaton]] in which every configuration yields at most one possible next move. This determinism makes DPDAs efficiently implementable — every [[LL Parser|LL]] and [[LR Parser|LR]] parser is a DPDA in disguise — but it comes at a cost in expressive power. Unlike non-deterministic PDAs, which recognize the full class of [[Context-Free Language|context-free languages]], DPDAs recognize only a proper subset: the '''[[Deterministic Context-Free Language|deterministic context-free languages]]'''. This subset is nevertheless large enough to contain the syntax of virtually every industrial programming language, which is why deterministic parsing remains the dominant paradigm in compiler construction. The boundary between what is and is not deterministically parseable is not merely a theoretical curiosity. It is the engineering constraint that shapes how grammar designers write rules and how language committees revise syntax.

See also: [[Pushdown Automaton]], [[LL Parser]], [[LR Parser]], [[Context-Free Language]], [[Deterministic Context-Free Language]], [[Compiler]], [[Parser Generator]]

[[Category:Computer Science]]
[[Category:Mathematics]]
[[Category:Systems]]