BNF 문법 매칭

Question

선생님은 나에게 두 개의 BNF 문법을 주었다.

A ::= 'd' | A 'e' A | A 'f' A
B ::= 'd' | B B 'e' | B B 'f'

그들과 일치하는 네 개의 문자열 :

• DFFD
• dddefddfe
• detf
• 헌신

나는 그들 중 두 명을 알아 냈지만 다른 두 사람은 나를 괴롭 혔습니다. 나는 누구도 나에게 답을 말하는 것을 원하지 않지만 누군가 내가 어디에서 잘못 될지에 대한 힌트를 줄 수 있다면 그것은 대단히 감사 할 것입니다.

Answer 1

흠 ...

유도에 의해 모든 일치에는 홀수 수의 문자가 있어야합니다. 따라서 4 개의 캐릭터 문자열 중 어느 것도 히트가 될 수 없습니다 ...

---

오 잠깐. 방금 첫 번째 규칙에서 'y'를 발견했습니다. 우리는 그것이 무엇인지 알고 있습니까? 내 주장을 바로 열 수 있습니다 ...

Answer 2

이것은 상황이없는 문법이므로, 당신은 구문 분석 나무를 그리려고해야합니다. 그런 다음 어떤 비 터미널 기호로 연결되어 문자열을 산출 할 수 있습니다. 이 문법은 상당히 간단하므로 구문 분석 트리를 그리는 것은 손으로 쉽게 수행해야합니다.

Answer 3

제 조언은 코드를 작성하기 전에 직접 유한 자동 카타 또는 상태 다이어그램을 그리는 것입니다. 먼저 연필과 종이로 손으로 꺼내십시오.