컴파일러

기본 정의알파벳(alphabet)심벌들의 유한 집합ex) T={a,b,c,....,z}스트링(string) (또는 문장, 단어)알파벳 T에 속하는 하나 이상의 심벌들의 나열길이(length)스트링을 이루는 심벌들의 개수|w|로 표시empty string스트링의 길이가

정규 문법 이론컴파일러 어휘 분석 과정에서 모형을 만드는데 사용Type 3 문법RLG: A->tB, A->tLLG: A->Bt, A->t여기서 A,B는 V_N의 원소, t는 V_T\*의 원소우선형 형태의 규칙과 좌선형 형태의 규칙이 혼합되어 있으면 정규 문법이 아니다.