정규식 구문 분석 유형 -3 문법

Question

독해 Chomsky hierarchy ... ... regexp는 형식 2 문법 (문맥 자유 문법)을 구문 분석 할 수없고 유형 1과 유형 0도 파싱 할 수 없다는 것을 알고 있습니다. 일반 표현식은 모든 유형 3 문법 (regular grammars)을 구문 분석/catch 할 수 있습니까?

Answer 1

예, 교대, 연결 및 Kleene 별을 지원해야합니다. 이것은 PCRE (Perl/Java/JavaScript/PHP/...) 유형의 정규 표현식의 경우입니다. 대체는 ((...)|(...))으로, 연결은 (...)(...)으로, 그리고 Kleene 별은 (...)*으로 구현됩니다. (이들 중 대부분의 언어에서 —은 \A 및 \z과 같이 "start-of-string"및 "end-of-string"을 나타낼 때 필요하며 정규 문법에서 부여되는 숫자는 —입니다. 하지만 그 아이디어입니다.)

프로그래밍 컨텍스트에서 "정규 표현식"이라고 불리는 모든 것이 반드시 위의 모든 것을 가지고있는 것은 아닙니다. 예를 들어, POSIX Basic Regular Expressions은 교대로 모든 "브랜치"가 단일 문자로 구성되어있는 매우 제한된 형식의 교대 만 지원합니다 (예 : PCRE는 (a|b|c)이고 특수 문자는 [abc], POSIX BRE는 [abc] 임). (ab|c)과 같은 것을 표시 할 수 없습니다.