<p>I'm hoping to further understand how grammars are used in building recognizers for languages. Specifically, I know that a grammar defines the syntax of a language, but I'm confused about how this applies to recognizers.</p>
<ol>
<li>How does a recognizer use grammar to determine whether a string belongs to a language?</li>
<li>Is there a standard process or algorithm that recognizers follow when working with grammars?</li>
</ol>
<p>Also are there differences in how various types of grammars (like regular or context-free grammars) are used for building recognizers?</p>
<p>Any answers that can be provided to these questions would be appreciated.
Thank you.</p>

<grammar>
How is grammar used for recognizers?
CC BY-SA 4.0
2024-10-11T06:01:04.640Z
"are there differences in how various types of grammars (like regular or context-free grammars) are used for building recognizers?" Definitely yes, and that makes the first part of this question very broad. Are you asking how to translate from a formal grammar into a finite state machine acceptor for the language defined by that grammar? If so, probably you need to narrow it down to a specific kind of language. Are you thinking of practical systems? Note also that [cs.se] will have questions about the formal side (they are ok here too, just noting the answer you want may already be there).
Michael Homer
CC BY-SA 4.0
2024-10-11T12:04:38.557Z
By "recognizer" do you mean [**parser**](https://stackoverflow.com/questions/1788796/what-is-parsing)? That may help you search. There are different kinds of parsing algorithms (LL and LR, which are divided into LL(1), LL(k), etc. and SLR, LALR, etc.), and algorithms that take a grammar in BNF or other form and generate said kinds of parser from it.
tarzh
CC BY-SA 4.0
2024-10-11T16:40:18.607Z
Take a step back. Suppose you were given a grammar. Here's one: "EXP is either a base 10 integer, or EXP * EXP, or ( EXP )".  Now suppose I gave you a string "1 * (2 * "  How would YOU, a person, determine that the string is not a member of the language defined by the grammar for the EXP language?  *Somehow* you did that; what steps did you take?  By doing toy examples "by hand" you'll get insights into how to write a program that automates your thought process.
Eric Lippert
CC BY-SA 4.0
2024-10-12T15:44:32.667Z
Typically, a grammar is consumed by a ***parser generator*** (like ANTLR or YACC) in the category of [compiler-compilers](https://en.wikipedia.org/wiki/Compiler-compiler), not by a parser or recognizer itself.  The parser generator constructs a parser by reading a grammar.  That parser can then recognize the language described by the grammar.  The parser is constructed by the parser generator to incorporate all the rules (productions/recognitions) that were in the grammar.  Those rules are stored in tables and code in the generated parser program.
Erik Eidt
CC BY-SA 4.0
2024-10-14T22:54:58.540Z
Oh yeah, sorry. I did mean parser. Thank you all so much for the explanations, though. They really help!
Joe
# How is grammar used for recognizers?
Posted by: username_0 on 2024-10-11
I'm hoping to further understand how grammars are used in building recognizers for languages. Specifically, I know that a grammar defines the syntax of a language, but I'm confused about how this applies to recognizers.

1. How does a recognizer use grammar to determine whether a string belongs to a language?
2. Is there a standard process or algorithm that recognizers follow when working with grammars?

Also are there differences in how various types of grammars (like regular or context-free grammars) are used for building recognizers?

Any answers that can be provided to these questions would be appreciated.
Thank you.
**Tags:** grammar
> **Comments:**
> **username_1**: "are there differences in how various types of grammars (like regular or context-free grammars) are used for building recognizers?" Definitely yes, and that makes the first part of this question very broad. Are you asking how to translate from a formal grammar into a finite state machine acceptor for the language defined by that grammar? If so, probably you need to narrow it down to a specific kind of language. Are you thinking of practical systems? Note also that [cs.se] will have questions about the formal side (they are ok here too, just noting the answer you want may already be there).  
> **username_2**: By "recognizer" do you mean [**parser**](https://stackoverflow.com/questions/1788796/what-is-parsing)? That may help you search. There are different kinds of parsing algorithms (LL and LR, which are divided into LL(1), LL(k), etc. and SLR, LALR, etc.), and algorithms that take a grammar in BNF or other form and generate said kinds of parser from it.  
> **username_3**: Take a step back. Suppose you were given a grammar. Here's one: "EXP is either a base 10 integer, or EXP * EXP, or ( EXP )".  Now suppose I gave you a string "1 * (2 * "  How would YOU, a person, determine that the string is not a member of the language defined by the grammar for the EXP language?  *Somehow* you did that; what steps did you take?  By doing toy examples "by hand" you'll get insights into how to write a program that automates your thought process.  
> **username_4**: Typically, a grammar is consumed by a ***parser generator*** (like ANTLR or YACC) in the category of [compiler-compilers](https://en.wikipedia.org/wiki/Compiler-compiler), not by a parser or recognizer itself.  The parser generator constructs a parser by reading a grammar.  That parser can then recognize the language described by the grammar.  The parser is constructed by the parser generator to incorporate all the rules (productions/recognitions) that were in the grammar.  Those rules are stored in tables and code in the generated parser program.  
> **username_0**: Oh yeah, sorry. I did mean parser. Thank you all so much for the explanations, though. They really help!  
---
## 0 answers
