Skillnad mellan Regular Expression och Context Free Grammar
Share
De huvudskillnad mellan regelbundet uttryck och kontextfri grammatik är att Vanliga uttryck hjälper till att beskriva alla strängar i ett vanligt språk medan kontextfri grammatik hjälper till att definiera alla möjliga strängar i ett kontextfritt språk.
Grammatik betecknar syntaktiska regler för konversation på naturliga språk. Datavetenskap använder i stor utsträckning teorin om formella språk. År 1956 gav Noam Chomsky en matematisk modell av grammatik för att skriva datorspråk. När det är möjligt att härleda en uppsättning av alla strängar från en grammatik sägs att språket genereras av den grammatiken. Två typer av grammatik är vanlig grammatik och kontextfri grammatik. Varje språk som kan beskrivas med ett reguljärt uttryck är ett vanligt språk. Kontextfri grammatik är en generalisering av regelbundet uttryck. Det är möjligt att använda vanliga uttryck för att skriva vanliga språk och kontextfri grammatik för att skriva kontextfri grammatik.
Viktiga områden som omfattas
1. Vad är Regular Expression
- Definition, exempel
2. Vad är Context Free Grammar
- Definition, exempel
3. Förhållande mellan regelbunden uttryck och kontextfri grammatik
- Föreningens sammanfattning
4. Skillnad mellan Regular Expression och Context Free Grammar
- Jämförelse av viktiga skillnader
Nyckelbegrepp
Regelbunden uttryck, kontextfri grammatik
Vad är Regular Expression
Den vanliga grammatiken genererar vanliga språk. Denna grammatik har en enda icke-terminal på vänster sida och en högra sida som består av en enda terminal eller en enda terminal följt av en enda icke-terminal. Det kan ha en produktionsregel enligt följande.
X -> a eller X -> a Y
Där X, Y e N (icke-terminal) och en E (terminal)
Regelbundna uttryck hjälper till att skriva regelbunden grammatik för att beskriva vanliga språk.
Ett regelbundet uttryck representerar en viss uppsättning strängar på ett algebraiskt sätt. Några viktiga regler att följa när du skriver ett regelbundet uttryck är som följer.
- Terminalsymbolerna, nollsymbolen och den tomma symbolen är reguljära uttryck.
- Förbundet av två reguljära uttryck är ett reguljärt uttryck.
- Sammanfattningen av två reguljära uttryck är ett reguljärt uttryck.
- Iteration eller stängning är ett reguljärt uttryck.
Det reguljära uttrycket för uppsättningen 0,1,2 är som följer.
R = 0 + 1 + 2
Satsen abb, a, b, bba kan representeras av följande reguljära uttryck.
R = abb + a + b + bba
Tänk på uppsättningen, ε, 0, 00, 000, ...
E är den tomma strängen. Den vanliga uttrycket är R = 0 *. Detta representerar stängningen av symbolen inklusive den tomma symbolen.
I uppsättningen 1, 11, 111, 1111, ...
Det reguljära uttrycket är R = 1 +. Denna + betecknar stängning av en symbol exklusive den tomma symbolen.
Vad är Context Free Grammar
I formell språkteori är Context Free Language (CFL) ett språk som genereras av Context Free Grammar. Fyra parametrar definierar kontextfri grammatik (G).
G = V, Σ, S, P
V: Sats med variabla eller icke-terminala symboler.
Σ: Sats med terminalsymboler
S: Start Symbol
P: Produktionsregeln
Kontextfri grammatik har följande format för produktionsregeln.
A -> a där a = V, Σ * och A ε V
Ett exempel på Context Free Grammar är som följer. Varje produktion består av en icke-terminal symbol och ett reguljärt uttryck.
För att generera ett språk som genererar lika många a och b är i formatet anbn. Kontextfri grammatik är som följer.
G = (S, A), (a, b), (S -> aAb, A -> aAb | e)
Med tanke på startsymbolen,
S -> a A b
Genom att tillämpa A -> aAb
→ a a A b b
Genom att ange A -> aAb igen,
→ a a a A b b b
Genom att använda A -> ε (Denna symbol betecknar en tom sträng)
→ a a a b b b
→ a 3 b 3
När man överväger utgången är antalet a s lika med antalet b s. Den har an bn form.
Förhållande mellan regelbunden uttryck och kontextfri grammatik
- Kontextfri grammatik är en generalisering av reguljära uttryck.
Skillnad mellan Regular Expression och Context Free Grammar
Definition
Ett reguljärt uttryck är ett begrepp i formell språkteori som är en sekvens av tecken som definierar ett sökmönster. Context Free Grammar är en typ av formell grammatik i formell språkteori, som är en uppsättning produktionsregler som beskriver alla möjliga strängar på ett givet formellt språk.
Användande
Regelbundna uttryck hjälper till att representera vissa uppsättningar av strängar på ett algebraiskt sätt. Det bidrar till att representera vanliga språk. Kontextfri grammatik hjälper till att definiera alla möjliga strängar i ett kontextfritt språk.
Slutsats
Ett vanligt uttryck är en metod för mönstermatchning. Det är en flexibel metod för att tillhandahålla ett flexibelt och kortfattat sätt att matcha textsträngar. Det definierar alla strängar i det vanliga språket. Å andra sidan tillåter kontextfri grammatik att definiera alla strängar som tillhör ett kontextfritt språk. Skillnaden mellan reguljärt uttryck och kontextfri grammatik är att de reguljära uttrycken hjälper till att beskriva alla strängar i ett vanligt språk medan kontextfri grammatik bidrar till att definiera alla möjliga strängar i ett kontextfritt språk.
Referens:
1. "Regular Expressions." Www.tutorialspoint.com, Tutorials Point, 8 Jan. 2018, Tillgänglig här.
2. "Context-Free Grammar Inledning." Www.tutorialspoint.com, Tutorials Point, 8 Jan. 2018, Tillgänglig här.
Image Courtesy:
1. "Toolbaricon RegEx" Av M0tty - Egent arbete (CC BY-SA 4.0) via Commons Wikimedia
