정규 표현식을 어셈블리로 변환하는 방법은 무엇입니까?

Question

C가 어셈블리로 변환 된 다음 어셈블리가 기계 코드로 변환된다는 것을 알았습니다. 포인터와 루프와 같은 기본 C 구문을 32 비트 MIPS 어셈블리로 변환하는 방법을 배웠습니다. 하지만 예를 들어 C에서 정규 표현식을 어셈블리로 변환하는 방법을 배우지 못했지만 거기에는 조리법이 있습니까?

Answer 1

어셈블리 언어로 정규 표현식을 변환하는 것은 몇십 년 전에 스타일을 벗어난 것처럼 보입니다. 대신, 요즘은 일반적으로 비 결정적 유한 자동 기계 (NFA)로 중간 단계가있는 결정 론적 유한 자동 연산 (DFA)으로 컴파일됩니다. 당신이이 용어에 익숙하지 않은 경우, 참조 :

• http://en.wikipedia.org/wiki/Deterministic_finite_automaton
• http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

정규식에 해당하는 NFA는 아주 쉽게 구성되어; 정규식의 각 포인트를 상태로 간주하고 정규 표현식의 다음 포인트로 이동하여 해당 상태에서 다음 상태로 전환 할 수있는 문자 세트를 고려하십시오.

PCRE를 비롯한 다른 인기있는 정규식 엔진은 정규식을 컴파일하지 않지만 쓰기 쉽고 병적으로 메모리 사용량이 많습니다 (많은 재귀 호출 프레임, 스택 오버플로가 발생할 경우 if 실제 함수 호출로 구현 됨) 및 병리학 적으로 나쁜 big-O 성능 (지수 시간이 될 수 있음).

Answer 2

C는 regexes를 지원하지 않습니다. 조립도하지 않습니다. 패턴 매칭을위한 알고리즘 코드를 작성하고, 어셈블리/머신 코드에 아직 없다면 번역/컴파일하십시오. 마술은 없다.

Answer 3

일반적으로 정규식을 구현하는 방법에 따라 다릅니다. 다음과 같이 할 수 있습니다.

• PCRE 또는 POSIX 정규식과 같은 것을 사용하십시오. 이 경우이 API에 대한 함수 호출은 아키텍처/ABI와 관련된 호출 규칙을 사용하여 적절한 호출을 수행하여 단순히 기계 (어셈블리) 코드로 변환됩니다.
• flex과 같은 도구를 사용하십시오. 이 경우 도구는 일반적으로 테이블 및 상태 시스템의 형태로 많은 양의 C 코드를 생성하며이 코드는 컴파일러를 사용하여 변환됩니다.

임시 정규식 구문 분석 체계를 구현하면 컴파일러에서 코드에 대해 생성하는 모든 내용이 포함됩니다.